乘法逆元
定义
对于一个线性同余方程 \(ax \equiv 1 \pmod p\)，称 \(x\) 为 \(a \bmod p\) 下的逆元，可记作 \(a^{-1}\)。
求法
快速幂求逆元
我们需要使用费马小定理：
\[\begin{aligned} ax &\equiv 1 \pmod p\\ ax &\equiv a^{p - 1} \pmod p \\ x &\equiv a^{p - 2} \pmod p \end{aligned} \]那么我们就可以直接使用快速幂求解了。
扩展欧几里得求逆元
考虑将 \(ax \equiv 1 \pmod p\) 化成 \(ax + by = c\) 的形式。显然有 \(ax + kp = 1\)，那么直接带入扩展欧几里得求解即可。
线性递推
可以在 \(\mathcal{O(n)}\) 的时间复杂度内预处理出逆元。
令 \(p = k \cdot a + b\)，有 \(k \cdot a + b \equiv 0 \pmod p\)，此时为了构造出 \(a^{-1}\)，我们可以巧妙地给式子乘上一个 \(a^{-1} \cdot b^{-1}\)，则 \(k \cdot b^{-1} + a^{-1} \equiv 0 \pmod p\)，移项，\(a^{-1} \equiv -\lfloor \frac{p}{a} \rfloor \cdot (p \bmod a)^{-1} \pmod p\)，那么我们就可以愉快地递推了。
$\tt{Link}$
inv[0] = 1;
for (int i = 1; i <= n; ++ i )
inv[i] = (p - p / i) * inv[p % i] % p;