C++で2^(2^A) % Bを効率的に計算する方法

このチュートリアルでは、2^(2^A) % Bという式の値を求めるプログラムをC++で作成していきます。

一見すると巨大な指数計算が必要に思えますが、再帰関数を使うことで、実際に巨大な数を計算することなく効率的に答えを求められます。ここでは、その考え方と実装手順を順番に解説します。

解き方の手順

この問題は、次のような性質を利用して再帰的に解くことができます。

• A と B の2つの引数を受け取る再帰関数を作成します。

  • A が 1 の場合、2^(2^1) % B = 4 % B となるため、4 % B を返します（ベースケース）。

  • それ以外の場合は、引数を A - 1 として関数を再帰的に呼び出します。

  • 得られた結果に対して「result * result % B」を計算して返します。これは (x^2) % B を意味し、指数を1段階ずつ戻しながら値を構築していきます。

• 最終的な結果を出力します。

なぜこの方法でうまくいくのか

2^(2^A) は A が大きくなると天文学的な桁数になるため、直接計算するのは現実的ではありません。しかし、モジュロ演算には (x * y) % B = ((x % B) * (y % B)) % B という重要な性質があります。この性質により、各段階で剰余を取りながら計算を進めることで、オーバーフローを避けつつ正確な答えを得ることができます。

サンプルコード

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
long long solveTheEquation(long long A, long long B) {
    // 2^(2^1) % B = 4 % B
    if (A == 1) {
        return (4 % B);
    }
    else {
        long long result = solveTheEquation(A - 1, B);
        return result * result % B;
    }
}
int main() {
    long long A = 37, B = 467;
    cout << solveTheEquation(A, B) << endl;
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

113

A = 37、B = 467 の場合、2^(2^37) % 467 の計算結果は 113 となります。このように、膨大な指数を持つ式でも再帰とモジュロ演算を組み合わせれば、瞬時に答えを求められるのです。

まとめ

本記事では、再帰関数とモジュロ演算の性質を活用して、2^(2^A) % B を効率的に計算する方法を紹介しました。このテクニックは競技プログラミングなどでも頻繁に登場するので、ぜひマスターしておきましょう。チュートリアルについて質問がある場合は、コメント欄でお気軽にお尋ねください。