给定 \(n\) 个正整数 \(a_i\)，求它们在模 \(p\) 意义下的乘法逆元。
逆元是模意义下的倒数，能够将模意义下无法直接计算的除法转化为乘法。
先来总结一下常用的求单个逆元的方法：
- 扩展欧几里得：\(O(\log n)\) 地求一个数的逆元，要求 \(a,p\) 互质即可（\(p\) 为模数），原理为解线性同余方程 \(ax\equiv 1(\bmod p)\)。
void exgcd(int a, int b, int& x, int& y) {
if (b == 0)
return x = 1, y = 0, void();
exgcd(b, a % b, y, x);
y = y - a / b * x;
}
//main
exgcd(a, p, inv, temp);
- 快速幂：根据费马小定理，当 \(p\) 为质数时，\(a\) 在模 \(p\) 意义下的逆元是 \(a^{p-2}\)，可直接用快速幂 \(O(\log n)\) 求解。
注意： 扩展欧几里得的条件是 \(a,p\) 互质即可，但快速幂法要求 \(p\) 必须是质数！
- 线性求逆元：显然 \(1^{-1}\equiv 1(\bmod p)\)，我们从 \(1\) 开始向后迭代求逆元。设 \(k=\lfloor\dfrac{p}{i}\rfloor，j=p\bmod i\)，有 \(p=ki+j\)。所以 \(ki+j\equiv 0(\bmod p)\)。两边同乘 \(i^{-1},j^{-1}\)，得到 \(kj^{-1}+i^{-1}\equiv 0(\bmod p)\)，所以要求的 \(i^{-1}=-kj^{-1}\)。因为 \(j=p\bmod i<i\)，而在迭代到 \(i\) 时，\([1,i)\) 的逆元都已经求出，则可以直接根据 \(j^{-1}\) 推出 \(i^{-1}\) 的值。
代码实现比较简单：
inv[1] = 1
for i in range(2, n + 1):
k = p // i
j = p % i
inv[i] = (p - k) * inv[j] % p # p-k 避免出现负数
- 线性求任意数逆元：当要求逆元的数不连续时（如本题中的情况），可以通过前缀积处理。
//求前缀积 s[i]
s[0] = 1;
for (int i = 1; i <= n; i++) s[i] = (long long)s[i - 1] * i % p;
// 费马小定理求 n 个数积的逆元（也就是逆元的积）
sv[n] = qpow(s[n], p - 2, p);
// 逐个消去 a[i] 的逆元，得到逆元前缀积
for (int i = n; i > 1; i--) sv[i - 1] = (long long)sv[i] * a[i] % p;
// 对于每个逆元前缀积，消去 a[1...i-1] 的逆元积，得到 a[i] 的逆元
for(int i = 1; i <= n; i++) inv[i] = (long long)sv[i] * s[i - 1] % p;
方法 4 可以解决本题，但还有更为简便的方法：直接通分。设 \(x = \prod a_i\)，原式 \(\sum\limits_{i=1}^{n}\dfrac{k^i}{a_i}(\bmod p)=\dfrac{\sum\limits_{i=1}^{n}k^i \dfrac{x}{a_i}}{x}\)，其中 \(\dfrac{x}{a_i}\) 可以通过预处理前后缀积求出，只需要求一次 \(x\) 的逆元即可。