剰余群逆元漸化式の導出

剰余群での除算ではユークリッドの互除法で逆元を求めているが、これは一つの計算にO(log(N))かかる。

まとめて逆元テーブルを作る場合には、ひとつO(1)、ぜんぶでO(N)で作る漸化式がある

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

code:python

for i in range(2, P):

q, r = divmod(P, i)

INVi = -INVr * 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の逆元を掛ける

$ -qr^{-1} \equiv a^{-1}

aの逆元を、aより小さいrの逆元を用いて求めることができた

小さい順に逆元を求めていけば良い