GCD(a^n, c) বের করা বড় সংখ্যা হ্যান্ডল করে (C++)

a, n, c যত বড় হতে পারে 10^9। a^n অতি বড় হতে পারে, তাই ডায়রেক্ট GCD সম্ভব নয়। মডুলার এক্সপোনেনশিয়েশন (O(log n)) ব্যবহার করে a^n mod c বের করুন, তারপর GCD(a^n mod c, c) করুন।

উদাহরণ

#include <iostream>
#include <algorithm>
using namespace std;

long long power(long long a, long long n, long long mod) {
    long long res = 1;
    a %= mod;
    while (n) {
        if (n & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        n >>= 1;
    }
    return res;
}

long long bigGCD(long long a, long long n, long long b) {
    if (a % b == 0) return b;
    long long mod_exp = power(a, n, b);
    return __gcd(mod_exp, b);
}

int main() {
    long long a = 10248585, n = 1000000, b = 12564;
    cout << "GCD value is: " << bigGCD(a, n, b);
    return 0;
}

আউটপুট

GCD value is: 9