线性求逆元

已知一个质数$M$，求出$1→n$中每个数关于模$M$的逆元，时间复杂度$O(n)$ 公式： ### $inv[i]=(M-\lfloor{M/i}\rfloor)\times inv[M\%i]\%M$ 推导如下： 设$i\in[1,n],t=\lfloor{M/i}\rfloor,k=M\%i$ $\qquad\qquad\qquad\qquad\qquad\because t\times i+k\equiv0\ (mod\ M)$ $\qquad\qquad\qquad\qquad\qquad\therefore -t\times i\equiv k\ (mod\ M)$ 同除$i\times k\qquad\qquad\Rightarrow -t\times inv[k]\equiv inv[i]\ (mod\ M)$ 再将$t,k$代入 $\qquad\qquad\qquad\Rightarrow -\lfloor{M/i}\rfloor\times inv[M\%i]\equiv inv[i]\ (mod\ M)$ 将$mod\ M$代入转化为等式 $\qquad\qquad\qquad\Rightarrow inv[i]=(M-\lfloor{M/i}\rfloor)\times inv[M\%i]\%M$ 推导完毕