「数论」线性求所有逆元的方法

前几天在看 lucas 定理的时候发现要求 $1,~2,\cdots,p-1\bmod p$ 的逆元，然后就看到了一个 $\Theta(n)$ 的做法。

这个做法实际上是这样的，首先我们知道 $1^{-1} \equiv 1 \pmod p$，然后我们设 $p = k\cdot i + r,~r < i,~1 < i < p$，再将这个式子放到 $\mathrm{mod}\,\, p$ 意义下就会得到

\[k\cdot i + r \equiv 0 \pmod p\]

两边同时乘上 $i^{-1}\cdot r^{-1}$ 就会得到

\[\begin{eqnarray*} k\cdot r^{-1} + i^{-1} &\equiv& 0 &\pmod p\\ i^{-1} &\equiv& -k\cdot r^{-1} &\pmod p\\ i^{-1} &\equiv& -\left\lfloor\frac{p}{i}\right\rfloor\cdot \left(p\bmod i\right)^{-1} &\pmod p\ \end{eqnarray*}\]

于是就可以从前面推出当前的逆元了，代码也就一行

A[i] = -(p / i) * A[p % i];