ধরুন আমাদের একটি অ্যারে A আছে, যার Nটি উপাদান। আমাদের অ্যারে সব উপাদানগুলির ফ্যাক্টোরিয়ালের GCD বের করতে হবে। ধরুন উপাদানগুলো হল {3, 4, 8, 6}, তবে ফ্যাক্টোরিয়ালের GCD হল ৬। এখানে আমরা একটি ট্রিক দেখব। যেহেতু দুটি সংখ্যার GCD হলো সে সবচেয়ে বড় সংখ্যা যা দুটোকে ভাগ করে, তাই দুটি সংখ্যার ফ্যাক্টোরিয়ালের GCD হলো ছোট সংখ্যাটির ফ্যাক্টোরিয়ালই। তাই 3! এবং 5!-এর GCD হল 3! = ৬।
C++ প্রোগ্রাম উদাহরণ
#include <iostream>
using namespace std;
long fact(int n){
if(n <= 1)
return 1;
return n * fact(n-1);
}
int gcd(int arr[], int n) {
int min = arr[0];
for (int i = 1; i < n; i++) {
if(min > arr[i])
min = arr[i];
}
return fact(min);
}
int main() {
int arr[] = {3, 4, 8, 6};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "GCD: " << gcd(arr, n);
return 0;
}
আউটপুট
GCD: 6
