C++で巨大な数aの(a^b) % mを計算する方法

このチュートリアルでは、非常に大きな数 a が与えられたときに、(a^b) % m を効率的に計算する方法を解説します。桁数が数十桁を超えるような巨大な整数は、標準の整数型では扱えないため、文字列として受け取りながら処理するのがポイントです。

基本となる考え方

剰余演算の性質から、次の等式が成り立ちます。

(a^b) % m = (a % m) × (a % m) × … × (a % m)（b回）

つまり、まず a % m の値を求めてしまえば、あとはそれを b 回掛け、毎回 m で剰余を取るだけで答えが得られます。これにより、巨大な数 a を直接扱う必要がなくなります。

解法の手順

• 数値 a（文字列）、b、m を初期化します。
• a % m を求める関数を作成します。
  • 結果を格納する変数を 0 で初期化します。
  • 文字列形式の数値を先頭から順に走査します。
  • 各桁の数字を「変数×10＋現在の桁」の形で加えていきます。
  • 毎ステップで mod を取り、値が大きくなりすぎないようにします。
• a % m の値を取得します。
• b 回繰り返すループを作成し、各回で「結果 × (a % m)」を計算して mod を取ります。
• 最終的な結果を出力します。

サンプルコード

実際のコードを見てみましょう。

#include<bits/stdc++.h>
using namespace std;

// 文字列で表された巨大な数 a の mod を計算する
unsigned int aModm(string str, unsigned int mod) {
    unsigned int number = 0;
    for (unsigned int i = 0; i < str.length(); i++) {
        number = number * 10 + (str[i] - '0');
        number %= mod;
    }
    return number;
}

// (a^b) % m を計算する
unsigned int aPowerBmodM(string &a, unsigned int b, unsigned int m) {
    unsigned int a_mod_m_result = aModm(a, m);
    unsigned int final_result = 1;
    for (unsigned int i = 0; i < b; i++) {
        final_result = (final_result * a_mod_m_result) % m;
    }
    return final_result;
}

int main() {
    string a = "123456789012345678901234567890123";
    unsigned int b = 3, m = 7;
    cout << aPowerBmodM(a, b, m) << endl;
    return 0;
}

実行結果

上記のプログラムを実行すると、次の出力が得られます。

1

計算量とさらなる最適化

この手法の時間計算量は O(b) です。b が小さい場合は十分ですが、b が非常に大きい場合（10⁹ 以上など）には非効率になります。そのようなケースでは、「繰り返し二乗法（バイナリ累乗）」を使うことで O(log b) まで高速化できます。指数 b を2進数に分解しながら累乗を組み合わせることで、乗算の回数を大幅に減らせる点がポイントです。

まとめ

巨大な整数は文字列として受け取り、剰余演算の性質を活かして段階的に mod を取ることで、オーバーフローを避けながら正確に計算できます。本記事の内容について質問がある場合は、コメント欄でお気軽にお尋ねください。