乘法逆元

如果尝试对取模后的结果直接进行除法运算，可能会出现除不尽的问题，
这时候就需要用到乘法逆元。
乘法逆元有着类似倒数的性质：对于正整数 $x$，如果存在正整数 $y$，满足
$xy ≡ 1 (mod$ $p)$
则 $x,y$ 互为模 $p$ 意义下的乘法逆元。
当我们想做除法运算时，可以用乘上对应的乘法逆元来代替。
当 $x$ 与 $p$ 互素时，存在唯一的 $x$ 的逆元。当 $p$ 是素数时，所有不是 $p$的倍数的整数都有唯一的逆元，所以大部分题目都会对素数取模。

扩展欧几里得算法求逆元

求逆元就是求如下方程的解：
$ax ≡ 1 (mod$ $p)$
也就是
$ax − kp = 1,k ∈ Z$
假如 $gcd(a, p) = 1$（也就是逆元存在的条件），就可以用扩欧来计算 $x$了。注意结果可能是负数，此时需要再加上 $p$。

利用费⻢小定理求逆元

根据费⻢小定理
$a^{p−1} ≡ 1 (mod$ $p)$
改写一下，就得到
$a · a^{p−2} ≡ 1 (mod$ $p)$
于是 $a^{p−2}$%$p$ 就是 $a$ 的逆元，可以通过快速幂来计算，也是非常实用的一种求逆元方法。