剰余群逆元漸化式の導出

剰余群での除算ではユークリッドの互除法で逆元を求めているが、これは一つの計算にO(log(N))かかる。 まとめて逆元テーブルを作る場合には、ひとつO(1)、ぜんぶでO(N)で作る漸化式がある

• inv[a] = MOD - inv[MOD % a] * (MOD / a) % MOD; python

for i in range(2, P):
    q, r = divmod(P, i)
    INV[i] = -INV[r] * q % P

導出 Pをaで割った商がq、余りがrだとする(q, r = divmod(P, a))

• 以下の式が成り立つ
• $P=aq+r$
• 両辺をmod Pする
• $0\equiv aq+r$
• aの逆元を掛ける
• $0\equiv q+a^{-1}r$
• qを移項する
• $-q\equiv a^{-1}r$
• rの逆元を掛ける
• $-q{r}^{-1}\equiv a^{-1}$
• aの逆元を、aより小さいrの逆元を用いて求めることができた
• 小さい順に逆元を求めていけば良い