【フェルマーの小定理】ABC228 - E - Integer Sequence Fair

すぐ忘れそうなのでなんとなくアウトプット。

ABC228 E問題: Integer Sequence Fair (diff 1579)

E - Integer Sequence Fair

提出したコード
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)

つぶやき

フェルマーの小定理は、逆元の計算に用いられることがあります。

「998244353 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita

Python の pow 関数を使うと累乗の高速計算もできる上に、逆元の計算もい瞬でできるので、この辺のアルゴリズムや知識の習得が甘くなりがち（？）。

実際に、拡張ユークリッドの互除法も最近知りましたし、繰り返し二乗法の実装もしたことがありません。

良いのか悪いのか。