Cần tìm GCD của hai số trong đó một số có thể lớn như (10^9 ^ 10^9), không thể lưu trữ trong kiểu long hay kiểu dữ liệu khác. Ví dụ a = 10248585, n = 1000000, b = 12564, kết quả GCD(a^n, b) sẽ là 9.
Do số quá lớn, không thể dùng thuật toán Euclid. Phải dùng lũy thừa modulo 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); }Kết quả
GCD value is: 9