gcd（a ^ n、c）を見つけます。ここで、a、n、cはC++で1から10^9まで変化します。

2つの数値のGCDを見つける必要があります。そのうちの1つの数値は（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