线性求逆元证明 | qkoqhh

背景

记得是打多校的时候学到了线性求所有逆元的方法，递推式如下

$\begin{eqnarray*} i^{-1}\equiv-\lfloor\frac{inf}{i}\rfloor(inf && mod && i)&&&(mod&inf) \end{eqnarray*}$

后面无意中发现证明方法，而且异常简单

原文请戳此处

证明

令 $inf=pi+r$ ，有

$\begin{eqnarray*} pi+r&\equiv&0&\pmod{inf} \end{eqnarray*}$

两边同乘 $i^{-1}\cdot r^{-1}$

$\begin{eqnarray*} pr^{-1}+i^{-1}&\equiv&0&\pmod{inf} \\ i^{-1}&\equiv&-pr^{-1}&\pmod{inf} \\ i^{-1}&\equiv&-\lfloor\frac{inf}{i} \rfloor(inf\bmod i)&\pmod{inf} \end{eqnarray*}$

代码

也是异常简单

1	`for(int i=1;i<=n;i++)inv[i]=inv[inf%i]*(inf-inf/i)%inf`