Chúng ta phải tìm GCD của hai số trong đó một số có thể lớn bằng (109 ^ 109), không thể được lưu trữ trong một số kiểu dữ liệu như long hoặc bất kỳ số nào khác. Vì vậy, nếu các số là a =10248585, n =1000000, b =12564, thì kết quả của GCD (a ^ n, b) sẽ là 9.
Vì các số rất dài nên chúng ta không thể sử dụng thuật toán Euclide. Chúng ta phải sử dụng lũy thừa mô-đun với độ phức tạp O (log n).
Ví dụ
#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); }
Đầu ra
GCD value is: 9