Pythonで2^(2^p) mod qを効率的に計算するプログラム

問題の概要

2つの整数 p と q が与えられたとします。このとき、2^(2^p) mod q の値を求める必要があります。出力は整数でなければなりません。

例えば、入力が p = 5、q = 6 の場合、出力は 4 になります。

解決のアプローチ

この問題を解くためには、以下の手順に従います。

• res := 2^(2^p) mod q を計算する
• res を返す

ここで重要なのは、Pythonの組み込み関数 pow() を使う点です。pow(base, exp, mod) のように3つの引数を渡すことで、冪乗を計算した後に剰余を取る処理を高速なモジュラー指数計算として実行してくれます。巨大な数を一度計算してから剰余を取るのに比べ、メモリ消費と計算時間を大幅に抑えられるのが大きな利点です。

実装例

それでは、以下の実装を見て理解を深めましょう。

def solve(p, q):
   res = pow(2, 2 ** p, q)
   return res

print(solve(5, 6))

入力

5, 6

出力

4

コードの解説

関数 solve(p, q) では、pow(2, 2 ** p, q) を呼び出しています。これは「2 を (2^p) 回掛けた結果を q で割った余り」を意味します。p = 5 の場合、指数部分は 2^5 = 32 となり、2^32 mod 6 = 4 が計算されます。

仮に通常の冪乗演算（**）だけで計算すると、p が大きくなるにつれて中間の数値が爆発的に大きくなり、処理が非常に遅くなります。しかし、pow() の第3引数を使えば、各段階で剰余を取りながら計算が進むため、p が非常に大きい場合でも効率的に答えを得られます。

まとめ

本記事では、Pythonの pow() 関数を活用して 2^(2^p) mod q を求める方法を紹介しました。モジュラー指数計算は競技プログラミングや暗号理論の分野でも頻繁に登場するテクニックなので、ぜひ覚えておきましょう。