はじめに
こんにちは！！競技プログラミングをやっている高校生のButterFlvです！今回は $\pmod{p}$ で $N$ 以下の正整数の逆元を $O(N)$ で列挙する方法を書いていきます。かなり有名な手法ですが備忘録として書きます。証明がかなり面白いです！！
忙しい人向け
- 配列 $\mathrm{inv}$ を用意します.
- $\mathrm{inv}[1]=1$ を初期値として与えます.
- 以下のループを $i=2,3,\cdots ,N$ で実行します.
- $\mathrm{inv}[i]=-(p\ /\ i)\cdot \mathrm{inv}[p\ \% \ i]\ \% \ p$
- $\mathrm{inv}[i]$ にアクセスすれば$\pmod{p}$ における $i\ (1\le i\le N)$ の逆元を $O(1)$ でとってくることができます.
証明
$a$ を $b$ で割った商を $a\ /\ b$ , 余りを $a\ \% \ b$ とする.
逆元を考えたい正整数 $a\ (\ge 2)$ についての動的計画法を考える. 今回は正整数 $1,2,\cdots ,a-1$ についてこれらの$\pmod{p}$における逆元 $1^{-1},2^{-1},\cdots ,(a-1)^{-1}$ がすでに求まっているとする.
$q=p\ /\ a,\ r=p\ \% \ a$ とおくと $p=a\cdot q + r$ が成立するので, この両辺の$\pmod{p}$を考えると
$$
\begin{align}
p&\equiv a\cdot q + r \\
0&\equiv a\cdot q + r \\
r&\equiv -a\cdot q \\
a^{-1}&\equiv -q\cdot r^{-1}
\end{align}
$$
以上より $r^{-1}$ が求まっていれば $a^{-1}$ は求まる. ここで, $r=p\ \% \ a$ としたことから $1\le r\le a-1$ が成立しており, $r^{-1}$ は動的計画法の仮定からすでに求まっている.
したがって, 乗算および剰余演算の時間計算量 $O(1)$ を仮定すれば $a^{-1}$ は $O(1)$ で計算できた. $a=2,3,\cdots ,N$ と順に計算していけばすべて合わせて $O(N)$ である.
おわりに
- この方法を使えば$\pmod{p}$における $N$ 以下の正整数の階乗の列挙が $O(N)$ でできるため正整数 $0\le a\le b\le N$ について $_ {a}\mathrm{C}_{b}$ を $O(1)$ で求めるための前計算も $O(N)$ でできます！！
- $a^{-1}\pmod{p}$ を求める他の有名な手法としては $a^{p-2}\pmod{p}$ を繰り返し二乗法で求めたり, 拡張ユークリッド互除法を用いて $ax+py=1$ の $x$ の解として求めたりする方法があります. （どちらも $O(\log p)$ ですが繰り返し二乗法が $\Theta (\log p)$ なのに対してユークリッド互除法で $\log p$ かかるのは最悪ケースの場合でほとんどの場合はもっと早く計算が終了するので拡張ユークリッド互除法のほうが早いとされています.）