求某个数的逆元，我们可以用log(n)的时间算出来。
但是，如果是求1~n的所有逆元呢？是不是就要用nlog(n)的时间了？
其实我们有一种线性的方法，可以在O(n)的复杂度求出1~n的逆元。
我们现在想要求1~n中一个数x的逆元
先假设模数y=ax+b
则ax+b
0 (%y)
将两边同时除以x·b （因为你的目的是得到一个形式为
……的式子）
则式子变为
拆开得a·
+
-a·
因为前面说了y=ax+b
所以a=
，b=（y%x）
将此带入，得：
-
`(y%x)^-1
我们设f[i]表示i的逆元，
则f[i]=(-y/i*f[y%i])%y
按照这个式子递推下去就可以得到1~n的逆元了。
当然也可以用递归的方式用log的时间求出n的逆元。