C++ में gcd(a^n, c) ढूंढें जहां a, n और c 1 से 10^9 तक भिन्न हो सकते हैं

हमें दो संख्याओं का GCD ढूंढना है जिनमें से एक संख्या (10⁹ ^ 10⁹) जितनी बड़ी हो सकती है, जिसे लॉन्ग या किसी अन्य डेटा टाइप में स्टोर नहीं किया जा सकता। तो यदि संख्याएं a = 10248585, n = 1000000, b = 12564 हैं, तो GCD(a^n, b) का परिणाम 9 होगा।

चूंकि संख्याएं बहुत लंबी हैं, हम यूक्लिडियन एल्गोरिदम का उपयोग नहीं कर सकते। हमें O(log n) जटिलता के साथ मॉड्यूलर एक्सपोनेंशिएशन का उपयोग करना होगा।

उदाहरण

#include 
#include 
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