求某個數的逆元，我們可以用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的逆元。