找到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