C++에서 주어진 배열 요소의 계승의 GCD 찾기

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

출력

GCD: 6