C++でGCD(a^n, c)を求める方法 ― a、n、cが1〜10^9の範囲の場合

本記事では、片方の数が (10^9)^(10^9) にもなり得るような巨大な2つの数の最大公約数（GCD）を求める方法を解説します。この規模の数値は、long型をはじめとする標準的なデータ型には格納できません。例えば、a = 10248585、n = 1000000、b = 12564 の場合、GCD(a^n, b) の結果は 9 になります。

数が非常に大きいため、通常のユークリッドの互除法を直接適用することはできません。そこで、O(log n) の計算量で実行できる「繰り返し二乗法（modular exponentiation）」を活用します。

解法の考え方

ここで重要となるのが、次の性質です。
GCD(a^n, b) = GCD(a^n mod b, b)
つまり、巨大な a^n を実際に計算する必要はなく、「a^n を b で割った余り」だけを求めればよいことになります。繰り返し二乗法を使えば、この剰余を O(log n) の計算量で効率的に求められます。

C++での実装例

#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

コードの解説

power関数は繰り返し二乗法を実装したものです。指数 n を2進数として扱い、ビットが立っている場合にのみ結果に現在の底を掛け、各ステップで底を2乗しながら剰余を取り続けることで、オーバーフローを防ぎつつ高速に計算します。

bigGCD関数では、まず a が b で割り切れるかどうかを判定します。割り切れる場合はGCDが b そのものになるため、そのまま b を返します。そうでなければ、power関数で a^n mod b を求め、その値と b のGCDを標準関数 __gcd で計算して返します。

この手法により、指数が10^9を超えるような巨大な場合でも、わずか O(log n) の計算量で正確にGCDを求めることができます。