Pythonで数日後の製品価格を計算するプログラム(剰余演算対応)

ある人が価格 x の製品を購入したいと考えているとしましょう。しかし、この製品は日が経つごとに価格が前日の x 倍に上昇していきます。そこで、購入を決意してから y 日後に製品の価格がいくらになっているかを求める必要があります。

価格が非常に大きな値になる場合は、答えを 10⁹ + 7 で割った余り(モジュロ)として出力します。入力はペア(タプル)のリストとして与えられ、各ペアの最初の値が初期価格 x、2番目の値が経過日数 y です。

たとえば、入力が以下の場合を考えてみます。

nums = [(5, 2), (6, 8), (2, 12), (2722764242812953792238894584, 3486705296791319646759756475), (1505449742164712795427942455727527, 61649494321438487460747056421546274264)]

このときの出力は 25, 1679616, 4096, 754504594, 32955023 となります。それぞれ 5² = 25、6⁸ = 1679616、2¹² = 4096 に対応し、巨大な数については 10⁹ + 7 で割った余りの値が返されています。

解法のアプローチ

この問題はシンプルなべき乗計算と剰余演算で解くことができます。手順は以下の通りです。

• i を 0 から nums の要素数まで繰り返す
• x, y にそれぞれ nums[i] の1番目と2番目の値を代入する
• x の y 乗を 10⁹ + 7 で割った余りを出力する

実装例

Python の組み込み関数 pow() は、3つの引数を渡すことで「べき乗の結果を指定した数で割った余り」を高速に計算できます。これはモジュラー指数演算(繰り返し二乗法)として内部で処理されるため、桁数が非常に大きい場合でも効率的に動作します。

def solve(nums):
    for i in range(len(nums)):
        x, y = nums[i][0], nums[i][1]
        print(pow(x, y, 1000000007))

solve([(5, 2), (6, 8), (2, 12),
       (2722764242812953792238894584, 3486705296791319646759756475),
       (1505449742164712795427942455727527, 61649494321438487460747056421546274264)])

入力

[(5, 2), (6, 8), (2, 12),
 (2722764242812953792238894584, 3486705296791319646759756475),
 (1505449742164712795427942455727527, 61649494321438487460747056421546274264)]

出力

25
1679616
4096
754504594
32955023

まとめ

毎日 x 倍に増加する価格を y 日分計算する問題は、結局のところ x^y mod (10⁹ + 7) を求めることに帰着します。Python では pow(x, y, 1000000007) と書くだけで、巨大な指数を持つべき乗の剰余を瞬時に算出できるため、競技プログラミングなどでも頻繁に活用されるテクニックです。