题解：P5431 【模板】模意义下的乘法逆元 2
shinzAnmono
·
·
题解
算法介绍
设所有 $b_i$ 的积为 $S$。
$$
\begin{aligned}
\left(\sum_{i=1}^{n}\dfrac{a_i}{b_i}\right)\bmod p&=
\frac{\left(\sum_{i=1}^{n}\dfrac{a_iS}{b_i}\right)}{S}\bmod p\\
&=\dfrac{\sum_{i=1}^n a_i\prod_{j=1}^{i-1}b_j\prod_{j=i+1}^nb_j}{S} \bmod p
\end{aligned}
$$
$O(N)$ 预处理出 $b_i$ 数组的前缀积和后缀积，使用费马小定理求一次逆元即可。
## 正确性证明
由上述描述，时间复杂度显然正确。当然，对于本题，需要边循环边维护 $k^i$。
## 参考代码
```cpp
#include<cstdio>
using ll = long long;
const int sz = 5e6 + 10;
ll pre[sz], suf[sz], arr[sz], mod, up, k, n;
inline ll qpow(ll base,ll exp){
ll ans=1;
while(exp!=0){
if(exp&1)ans=ans*base%mod;
base=base*base%mod,exp>>=1;
}
return ans;
}
inline ll read() {
char ch = getchar();
ll x = 0;
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9')
x = x * 10 + ch - '0', ch = getchar();
return x;
}
int main() {
n = read(), mod = read(), k = read();
pre[0] = 1;
for (register int i = 1; i <= n; i++)
arr[i] = read(), pre[i] = arr[i] * pre[i - 1] % mod;
suf[n + 1] = 1;
for (register int i = n; i; i--)
suf[i] = arr[i] * suf[i + 1] % mod;
for (register ll i = 1, p = k; i <= n; i++, p = p * k % mod)
up = (up + p * pre[i - 1] % mod * suf[i + 1] % mod) % mod;
printf("%lld\n", up * qpow(suf[1],mod-2) % mod);
return 0;
}
```