线性求逆元
我们知道 (1^{-1}equiv 1pmod p) ，然后我们设 (p=kcdot i+r,~r<i,~1<i<p) ，再将这个式子放到 (mathrm{mod}\,\,p) 意义下，就会得到：
[kcdot i+requiv 0pmod p
]
两边同时乘上 (i^{-1}cdot r^{-1}) 就会得到：
[egin{eqnarray*} kcdot r^{-1} + i^{-1} &equiv& 0 &pmod p\ i^{-1} &equiv& -kcdot r^{-1} &pmod p\ i^{-1} &equiv& -leftlfloorfrac{p}{i}
ight
floorcdot (pmod i)^{-1}&pmod pend{eqnarray*}
]
代码
inv[i]=((mod-mod/i)*inv[mod%i])%mod;