在 C++ 中查找给定数组元素阶乘的 GCD
c++server side programmingprogramming更新于 2025/3/15 9:52:17
假设我们有一个包含 N 个元素的数组 A。我们必须找到数组中所有元素阶乘的 GCD。假设元素为 {3, 4, 8, 6}，则阶乘的 GCD 为 6。这里我们将看到技巧。由于两个数字的 GCD 是最大的数字，它可以整除这两个数字，因此两个数字的阶乘的 GCD 是最小数字本身的阶乘值。因此 3！和 5！的 gcd 为 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);
}
输出
GCD: 6
