线性O(n)求1~n逆元

2019-04-14 20:01发布生成海报

站内文章 / 模拟电子

17532 0

求某个数的逆元，我们可以用log(n)的时间算出来。但是，如果是求1~n的所有逆元呢？是不是就要用nlog(n)的时间了？其实我们有一种线性的方法，可以在O(n)的复杂度求出1~n的逆元。先假设模数y=ax+b 则ax+b equiv

0 (%y) 将两边同时除以x·b （因为你的目的是得到一个形式为 $^{}$ $x^{-1}$ equiv

……的式子）则式子变为 $frac{ax+b}{x·b}$ equiv

0 拆开得a· $b^{-1}$ + $^{}$ $x^{-1}$ equiv

0 $x^{-1}$ equiv

-a· $b^{-1}$ 因为前面说了y=ax+b 所以a= $left lfloor frac{y}{x} ight floor$ ，b=（y%x）将此带入，得：
$x^{-1}$ equiv

- $left lfloor frac{y}{x} ight floor$ `(y%x)^-1 我们设f[i]表示i的逆元，则f[i]=(-y/i*f[y%i])%y 按照这个式子递推下去就可以得到1~n的逆元了。当然也可以用递归的方式用log的时间求出n的逆元。