NTL1B べき乗

はじめに

全問題の一覧はこちらです

Pythonでべき乗の計算をする場合は組み込み関数のpowを用いることができます。
ただし、下記のように愚直に実装すると間に合いません。

1	pow(m,n) % MOD

これはpow(m,n)が計算途中でとても巨大な数となってしまい、処理に時間がかかるためです。

しかし、合同式の性質からpow(m,n)計算の過程で剰余を取っても問題はありません。この工夫で計算途中で巨大な数になることを防げるはずです。

powにはそのための呼び出し方法が実装されており、pow(m,n,MOD)のように呼び出すことができます。

詳しくは公式リファレンスを参考にして下さい。なお、Pythonのpowは繰り返し二乗法で実装されています。

これらの考察から解答はいたってシンプルなコードになります。

1
2
3

MOD = 10**9+7
m, n = map(int, input().split())
print (pow(m,n,MOD))