线性求逆元

已知一个质数$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$

推导完毕


发表于 2018-05-11 20:49:07 in 笔记