जीसीडी (ए ^ एन, सी) खोजें जहां ए, एन और सी सी ++ में 1 से 10 ^ 9 तक भिन्न हो सकते हैं

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

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

उदाहरण

#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