剰余群逆元漸化式の導出
剰余群での除算ではユークリッドの互除法で逆元を求めているが、これは一つの計算にO(log(N))かかる。
まとめて逆元テーブルを作る場合には、ひとつO(1)、ぜんぶでO(N)で作る漸化式がある
inv[a] = MOD - inv[MOD % a] * (MOD / a) % MOD; pythonfor 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の逆元を掛ける
-qr^{-1} \equiv a^{-1}
aの逆元を、aより小さいrの逆元を用いて求めることができた
小さい順に逆元を求めていけば良い
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]