$a\times b\equiv 1(\mod p)​$ ,那么 $a,b​$ 互为对方$\mod p​$ 意义下的逆元。

法1：扩展欧几里得

$$

a\times b\equiv 1(\mod p)

$$

$$

a\times b+k\times p=1

$$

效率 $O(logn)​$

法2：费马小定理/欧拉定理

费马小定理：

若 $p$ 为质数，则有

$$

a^{p-1}\equiv 1(\mod p)

$$

$$

a^{p-2}\times a\equiv1(\mod p)

$$

所以 $a^{p-2}$ 就是 $a$ 在$\mod p$ 意义下的逆元。

欧拉定理：

若 $a,p$ 互质，则有

$$

a^{\varphi(p)}\equiv1(\mod p)

$$

$$

a^{\varphi(p)-1}\times a\equiv 1(\mod p)

$$

所以 $a^{\varphi (p)-1}$ 就是 $a$ 在$\mod p$ 意义下的逆元。

效率 $O(logp)$

法3：线性求逆元

（$p$ 需要是一个质数）

我们求 $i^{-1}$ 在$\mod p$ 意义下的值。

$$

p=k\times i+r

$$

令 $r<i$ 则 $k=\frac{p}{i},r=p\%i$

$$

k\times i+r\equiv 0(\mod p)

$$

同时除以 $i,r$

$$

k\times r^{-1}+i^{-1}\equiv 0(\mod p)

$$

$$

i^{-1}\equiv-k\times r^{-1}(\mod p)

$$

$$

i^{-1}\equiv-\frac{p}{i}\times inv[p\%i]

$$

$$

inv[i]=(p-\frac{p}{i})\times inv[p\%i]

$$

边界：$inv[1]=1$

效率 $O(n)$

法4：中国剩余定理

对于模数非质数的情况，

可以对模数质因数分解，让这个数对每个模数的每个因子求逆元，再用中国剩余定理合并。