Tìm GCD giai thừa của các phần tử của mảng đã cho trong C ++

Giả sử chúng ta có một mảng A, với N phần tử. Chúng ta phải tìm GCD thừa kế của tất cả các phần tử của mảng. Giả sử các phần tử là {3, 4, 8, 6}, khi đó GCD của các giai thừa là 6. Ở đây chúng ta sẽ xem mẹo. Vì GCD của hai số, là số lớn nhất, chia cả hai số, thì GCD của giai thừa của hai số là giá trị giai thừa của chính số nhỏ nhất. Vì vậy, gcd của 3! và 5! là 3! =6.

Ví dụ

#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);
}

Đầu ra

GCD: 6