Pythonでべき乗の剰余（mod）を計算するプログラムの書き方

3つの数値 x、y、z が与えられたとき、(x^y) % z を計算するのがこの記事のテーマです。べき乗の結果は指数が大きくなるほど爆発的に増加するため、剰余を取ることで値を扱いやすい範囲に収めることができます。これは競技プログラミングや暗号処理などでもよく使われる基本的なテクニックです。

例

入力：x = 2, y = 3, p = 3
出力：2

解説： 2^3 % 3 = 8 % 3 = 2 となります。

アルゴリズム

1. ステップ1： 3つの数値を入力として受け取る。
2. ステップ2： pow() 関数でべき乗を計算し、% 演算子で剰余を求める。
3. ステップ3： 結果を画面に表示する。

サンプルコード

x = int(input("Enter First Value ::>"))
y = int(input("Enter Second Value ::>"))
z = int(1e9+7)
# pow関数を使用してべき乗を計算
# その後、%演算子で剰余を求める
d = pow(x, y) % z
print("Value Is=", d)

実行結果

Enter First Value ::> 2
Enter Second Value ::> 3
Value Is= 8

このコードでは、まず x と y を標準入力から受け取り、法（モジュラス）として競技プログラミングで定番の 10^9 + 7 を設定しています。pow(x, y) でべき乗を計算した後、% z で剰余を取って結果を出力します。

より効率的な方法：pow() の第3引数を活用する

実は Python の組み込み関数 pow() は、第3引数に法を指定できるという便利な機能を持っています。pow(x, y, z) と書くだけで、巨大な中間値を生成することなく直接 (x^y) % z を計算できます。

x = int(input("Enter First Value ::>"))
y = int(input("Enter Second Value ::>"))
z = 10**9 + 7
# 3引数版のpow()で直接べき乗剰余を計算
d = pow(x, y, z)
print("Value Is=", d)

この方法には次のようなメリットがあります。

• メモリ効率： 巨大なべき乗の中間結果を保持しないため、メモリ消費を抑えられます。
• 処理速度： 内部で「繰り返し二乗法」が使われているため、指数が非常に大きくても高速に計算できます。
• コードの簡潔さ： 剰余演算を別途書く必要がなく、意図が明確になります。

競技プログラミングでは「答えを 10^9 + 7 で割った余りを求めよ」という問題が頻出です。そのような場面では、3引数版の pow() を使うのが最もシンプルかつ確実な解法となります。