[数论]线性求所有逆元的方法

前几天在看 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

再将这个式子放到\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*}

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

Read More