<p><a href="/ja/%E5%89%B0%E4%BD%99%E7%BE%A4%E3%81%A7%E3%81%AE%E9%99%A4%E7%AE%97">剰余群での除算</a>ではユークリッドの互除法で逆元を求めているが、これは一つの計算にO(log(N))かかる。
まとめて<a href="/ja/%E9%80%86%E5%85%83%E3%83%86%E3%83%BC%E3%83%96%E3%83%AB">逆元テーブル</a>を作る場合には、ひとつO(1)、ぜんぶでO(N)で作る漸化式がある</p>
<ul>
<li><code>inv[a] = MOD - inv[MOD % a] * (MOD / a) % MOD;</code>
python</li>
</ul>
<pre><code>for i in range(2, P):
    q, r = divmod(P, i)
    INV[i] = -INV[r] * q % P
</code></pre>
<p>導出
Pをaで割った商がq、余りがrだとする(<code>q, r = divmod(P, a)</code>)</p>
<ul>
<li>以下の式が成り立つ</li>
<li>$P = aq + r$</li>
<li>両辺をmod Pする</li>
<li>$0 \equiv aq + r$</li>
<li>aの逆元を掛ける</li>
<li>$0 \equiv q + a^{-1}r$</li>
<li>qを移項する</li>
<li>$-q \equiv a^{-1}r$</li>
<li>rの逆元を掛ける</li>
<li>$-qr^{-1} \equiv a^{-1}$</li>
<li>aの逆元を、aより小さいrの逆元を用いて求めることができた</li>
<li>小さい順に逆元を求めていけば良い</li>
</ul>


剰余群逆元漸化式の導出