O(n)求逆元
雨季
·
·
个人记录
O(n) 求逆元
公式：inv[i]=(p-p/i) \times inv[p\bmod i] \pmod p
证明：
令 p=i\times k+r ,
则在 \bmod p 的意义下，有 i\times k+r \equiv 0 \pmod p
等式两边同时乘上 i^{-1}\times r^{-1}，即 i^{-1}\times r^{-1}\times (i\times k+r) \equiv 0 \pmod p
则 k\times r^{-1}+i^{-1} \equiv 0 \pmod p
即i^{-1} \equiv -k\times r^{-1} \pmod p
由于 k= \Big\lfloor \frac{p}{i} \Big\rfloor\ ,\ r=p\bmod i
所以 i^{-1} \equiv -\Big\lfloor \frac{p}{i} \Big\rfloor \times (p\bmod i)^{-1}\pmod p
即 inv[i] \equiv -\Big\lfloor \frac{p}{i} \Big\rfloor \times inv[p\bmod i]\pmod p
则 inv[i] \equiv \Big(p -\Big\lfloor \frac{p}{i} \Big\rfloor\Big) \times inv[p\bmod i]\pmod p
得证 inv[i]=(p-p/i) \times inv[p\bmod i] \pmod p