线性求逆元

公式 && 食用方法

设$Inv(i)$表示$i$在模$M$意义下的逆元，则有：
$Inv(i) \equiv (-\lfloor{M\over i}\rfloor ) \times Inv(M \mod i)\mod M$
由于$(M\mod i )< i$，所以可以利用这个公式线性预处理出逆元。

当模数比较小的时候，可以预处理出$[0,M)$的所有数的逆元，然后算法的复杂度就可以少一个$\log M$~

---

推导过程

设$t=\lfloor{M\over i}\rfloor,k=M\mod i$。

则

$$t\times i +k \equiv 0 \mod M$$

即

$$- t\times i \equiv k \mod M$$

让左右两边同时除以一个$i\times k$：

$$- t\times Inv(k) \equiv Inv(i) \mod M$$

就得到了前面的公式

---

代码

inv[1]=1; for(int i=2;i<mod;++i) inv[i]=(mod-mod/i)*inv[mod%i]%mod;