สมมติว่าเรามีอาร์เรย์ A โดยมีองค์ประกอบ N เราต้องหา GCD ของแฟกทอเรียลของอิลิเมนต์ทั้งหมดของอาร์เรย์ สมมติว่าองค์ประกอบคือ {3, 4, 8, 6} จากนั้น GCD ของแฟกทอเรียลคือ 6 ที่นี่เราจะเห็นเคล็ดลับ เนื่องจาก GCD ของตัวเลขสองตัวนั้นเป็นจำนวนที่มากที่สุด ซึ่งหารตัวเลขทั้งสอง จากนั้น GCD ของแฟกทอเรียลของตัวเลขสองตัวจึงเป็นค่าของแฟกทอเรียลของจำนวนที่น้อยที่สุดนั้นเอง ดังนั้น gcd ของ 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
