比较暴力穷举、费马小定理与扩展欧几里得计算逆元的时空效率
在有理数算术中，除以一个数 $a$ 等同于乘上它的倒数 $1/a$。但在模算术中，由于我们只处理整数，没有小数，我们需要定义一个类似于倒数的概念，即模乘法逆元。
若整数 $a$ 和未知数 $x$ 满足同余式：
则称 $x$ 为 $a$ 模 $m$ 意义下的乘法逆元，记作 $a^{-1} \pmod m$ 或 $\text{inv}(a)$。这使得我们可以将同余式中的除法转化为乘法：
逆元存在的充要条件是 $a$ 与模数 $m$ 互质，即 $\gcd(a, m) = 1$。
遍历 $x \in [1, m-1]$ 测试 $ax \equiv 1 \pmod m$。复杂度 $O(m)$。
要求 $m$ 为质数，计算 $a^{m-2} \bmod m$。快速幂复杂度 $O(\log m)$。
求解线性方程 $ax + my = 1$ 的 $x$ 系数。适用于任意模数。复杂度 $O(\log (\min(a, m)))$。