乘法逆元是数论中重要的内容，也是 OI 中常用到的数论算法之一。
定义
在 $\text{mod p}$ 意义下我们把 $x$ 的乘法逆元写作 $x^{-1}$
$$x \times x^{-1} \equiv 1 \text{ (mod p)}$$
费马小定理
$$a^{p - 1} \equiv \text{ (mod p)}$$
要求 $p$ 为素数，上述公式可变为
$$a \times a^{p - 2} \equiv \text{ (mod p)}$$
由乘法逆元的定义，$a^{p - 2}$ 为 $a$ 的乘法逆元。
用快速幂计算 $a^{p - 2}$，总时间复杂度为 $O(\text{log }a)$
扩展欧几里得
扩展欧几里得（EXGCD）算法可以在 $O(\text{log max(a, b)})$ 的时间内求出关于 $x$,$y$ 的方程
$$ax + by = gcd(a, b)$$
的一组整数解
当 $b$ 为素数时有 $gcd(a, b) = 1$，直接求解就好了。
1 | inline long inv(const long num) { |
递推式
1 | inv[1] = 1; |
证明详见 Menci。
