定义

若 $ax \equiv 1 \pmod{b}$，则说 $x$ 是 $a \bmod b$ 的逆元，记为 $a^{-1}$。

求法

扩展欧几里得法

暂略

快速幂法

根据费马小定理，若 $gcd(a, p) = 1$，则 $a^{p-1} \equiv 1 \pmod{p}$。

因为 $ax \equiv 1 \pmod{b}$；

所以 $ax \equiv a^{b-1} \pmod{b}$；

所以 $x \equiv a^{b-2} \pmod{b}$。

线性求逆元

可以证明，在求解 $1, 2, \dots, n$ 中每一个自然数 $i$ 关于质数 $p$ 的逆元时，若 $i=1$，则 $i^{-1} \equiv 1 \pmod {p}$，否则 $i^{-1} \equiv - \lfloor \frac{p}{i} \rfloor (p \bmod i)^{-1} \pmod {p}$。

证明详见: 这里。

例题详见: 【模板】模意义下的乘法逆元。

线性求任意个数的逆元

可以先求出前缀积，在倒序求出每个前缀积的逆元。详见代码。

llint n, p;
std::vector<llint> a(n+3, 0), sum(n+3, 0), s(n+3, 0);
sum[0] = 1;
for(llint i = 1; i <= n; ++i) {
  sum[i] = (sum[i-1] * a[i]) % p; // 计算前缀积
}
s[n] = qpow(sum[n], p-2); // 使用快速幂法求出 s[n]
for(llint i = n-1; i; --i) {
  s[i] = (s[i+1] * a[i+1]) % p; // 抵消掉 a[i+1] 的逆元即可
}
// inv[i] = s[i] * sum[i-1] % p; // 最终结果

例题详见: 【模板】模意义下的乘法逆元 2。