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

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

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

Miskcoo's Space,版权所有丨如未注明,均为原创
转载请注明转自:http://blog.miskcoo.com/2014/09/linear-find-all-invert

miskcoo

顺利从福州一中毕业!感觉大学周围都是聚聚十分可怕QAQ 想要联系的话欢迎发邮件:miskcoo [at] gmail [dot] com

12 thoughts on “[数论]线性求所有逆元的方法

  1. 最后的 O(log p) 复杂度应该是对的,但是证明有问题,p是常量,所以小于 p mod i < p/2 并不能说明每一步折半,例如,p=n! -1 ,那么 p mod k = k-1 (k<n+1) 当然这种情况复杂度依然O(log p)。但怎么说明其复杂度为O(log p) ,我还不知道,当然平均复杂度是O(log p)是显然的。

  2. O(n)求所有逆元可以利用O(n)预处理所有阶乘的逆元然后用的时候乘一下就行了吧。。。蒟蒻只会用这样比较简单的做法。。

Leave a Reply

Your email address will not be published. Required fields are marked *

NOTE: If you want to add mathematical formulas, use $$ to wrap them. For example, use $$x_0$$ to get $$x_0$$.

If you want to get a newline, hit Enter twice, that is, use double newlines to get a newline.