设模数$p=k*i+r(r<i,i<p,k\in \operatorname{N*})$,则

$$k*i+r\equiv 0(mod ~p)$$

同乘$i^{-1}*r^{-1}$,有

$$i^{-1}\equiv -k*r^{-1}(mod~ p)$$

$$inv[i]\equiv -\left\lfloor\frac{p}{i}\right\rfloor *inv[p ~mod ~i](mod~ p)$$