เราต้องหา GCD ของตัวเลขสองตัว โดยที่หนึ่งตัวเลขอาจมีขนาดใหญ่เท่ากับ (109 ^ 109) ซึ่งไม่สามารถจัดเก็บไว้ในประเภทข้อมูลบางประเภทได้ เช่น แบบยาวหรือแบบอื่นๆ ดังนั้นหากตัวเลขเป็น a =10248585, n =1000000, b =12564 ดังนั้นผลลัพธ์ของ GCD(a^n, b) จะเป็น 9
เนื่องจากตัวเลขมีความยาวมาก เราจึงใช้อัลกอริทึมแบบยุคลิดไม่ได้ เราต้องใช้การยกกำลังแบบแยกส่วนกับความซับซ้อนของ O(log n)
ตัวอย่าง
#include<iostream>
#include<algorithm>
using namespace std;
long long power(long long a, long long n, long long b) {
long long res = 1;
a = a % b;
while (n > 0) {
if (n & 1)
res = (res*a) % b;
n = n>>1;
a = (a*a) % b;
}
return res;
}
long long bigGCD(long long a, long long n, long long b) {
if (a % b == 0)
return b;
long long exp_mod = power(a, n, b);
return __gcd(exp_mod, b);
}
int main() {
long long a = 10248585, n = 1000000, b = 12564;
cout << "GCD value is: " << bigGCD(a, n,b);
} ผลลัพธ์
GCD value is: 9
