在C ++中找到给定数组的元素阶乘的GCD

Z时代
2024-01-10
分类：综合

假设我们有一个包含N个元素的数组A。我们必须找到数组所有元素的阶乘的GCD。假设元素为{3，4，8，6}，那么阶乘的GCD为6。在这里我们将看到窍门。由于两个数的GCD是最大数，将两个数相除，因此两个数的阶乘的GCD就是最小数本身的阶乘的值。那么3的gcd！和5！是3！= 6。

示例

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