C++에서 a, n 및 c가 1에서 10^9까지 다양할 수 있는 gcd(a^n, c) 찾기

우리는 하나의 숫자가 (109 ^ 109)만큼 클 수 있는 두 숫자의 GCD를 찾아야 하며, 이는 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