【フェルマーの小定理】ABC228 - E - Integer Sequence Fair
すぐ忘れそうなのでなんとなくアウトプット。
ABC228 E問題: Integer Sequence Fair (diff 1579)
提出したコード
https://atcoder.jp/contests/adt_hard_20240529_3/submissions/54063234
$${M^{K^N}}$$を計算してね。$${\pmod {998244353}}$$
以下、$${P = 998244353}$$とします。
累乗を高速に計算するアルゴリズムとして繰り返し二乗法があり、Python の pow 関数がこれにあたります。
しかし、$${1 \le M, K, N \le 10^{18}}$$なので愚直な計算ができません。
""" TLE コード """
N, K, M = map(int, input().split())
mod = 998244353
ans = pow(M, pow(K, N), mod)
print(ans)
また、$${K^N \equiv a \pmod P}$$として必ずしも$${M^{K^N} \equiv M^a \pmod P}$$とならないので、以下のコードでは WA になります。
""" WA コード """
N, K, M = map(int, input().split())
mod = 998244353
ans = pow(M, pow(K, N, mod), mod)
print(ans)フェルマーの小定理
素数$${P}$$、$${P}$$の倍数でない整数$${M}$$に対して以下が成り立つ。
$$
M^{P - 1} \equiv 1 \pmod P
$$
これをフェルマーの小定理といいます。
本問題において$${M}$$が$${P}$$の倍数でない場合、$${K^N \equiv a \pmod{P-1}}$$とすると$${M^{K^N} \equiv M^a \pmod P}$$になります。
$${M}$$が$${P}$$の倍数であれば答えは$${0}$$です。
""" AC コード """
N, K, M = map(int, input().split())
mod = 998244353
if M % mod == 0:
print(0)
else:
ans = pow(M, pow(K, N, mod - 1),mod)
print(ans)つぶやき
フェルマーの小定理は、逆元の計算に用いられることがあります。
Python の pow 関数を使うと累乗の高速計算もできる上に、逆元の計算もい瞬でできるので、この辺のアルゴリズムや知識の習得が甘くなりがち（？）。
実際に、拡張ユークリッドの互除法も最近知りましたし、繰り返し二乗法の実装もしたことがありません。
良いのか悪いのか。