チラチラチラ裏

\主に競プロ備忘録/

累乗の中にmodを入れる操作

ab = ab mod p-1 (mod p) が成り立つ.

proof.

フェルマーの小定理より ap-1 = 1 (mod p)なので,mod pにおいて
ab
= a^( (p-1)(floor(b/(p-1)) +(b mod (p-1)))
= ( (ap-1)floor(b/(p-1))) * ab mod (p-1)
= ab mod (p-1)