在 C++ 中找到給定陣列元素階乘的最大公約數

假設我們有一個包含 N 個元素的陣列 A，我們必須找到該陣列所有元素階乘的最大公約數。假設元素為 {3, 4, 8, 6} 階乘的最大公約數為 6。接下來我們將看到這個技巧。因為兩個數的最大公約數是能同時整除這兩個數的最大數，所以兩個數的階乘的最大公約數是最小數的階乘值本身。因此，3! 和 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);
}

輸出

GCD: 6

Arnab Chakraborty

更新於:2019 年 10 月 21 日

329 次瀏覽

啟動你的 職業

完成課程獲得認證

開始