找到gcd（a ^ n，c），其中C，a，n和c在1到10 ^ 9之间变化

我们必须找到两个数字的GCD，其中一个数字可以和（109 ^ 109）一样大，而这些数字不能存储在long或任何其他数据类型中。因此，如果数字为a = 10248585，n = 1000000，b = 12564，则GCD（a ^ n，b）的结果将为9。

由于数字非常长，因此我们无法使用欧几里得算法。我们必须使用O（log n）复杂度的模幂。

示例

#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