M^(K^N) mod Pとフェルマーの小定理

[tipstar0125]

https://atcoder.jp/contests/abc228/tasks/abc228_e

[tipstar0125]

解説：https://atcoder.jp/contests/abc228/editorial/2932

[tipstar0125]

フェルマーの小定理：M^(P-1) = 1 (mod P) により、Mの(P-1)乗は1なので、K^Nを(P-1)で割った商は1になるので、余りだけを考えればよい。 よって、r = K^N mod (P-1)を求めて、M^r mod Pが答え。

[tipstar0125]

• コーナーケース：フェルマーの小定理はMとPが互いに素のときのみ成立するので、MがPの倍数の場合は、場合分けする必要がある
• オーバーフロー：MやKが10^18だと、繰り返し2乗法の計算の際、modをとる前にオーバーフローするので、u64では足りない。

[tipstar0125]

べき乗のべき乗のmod

M^(K^N) mod P

フェルマーの小定理：M^(P-1) = 1 (mod P) より、K^NはP-1毎に1になるので、K^NをP-1で割った余りのみを考えればよい。