B 3645 数列前缀和2 题解

· · 个人记录

题意很简洁清晰，就不简述了

解题思路

考虑每次询问的式子 \prod\limits_{i = l}^r a_i \bmod p，先不考虑模数，可以发现其等价于 \dfrac{\prod\limits_{i = 1}^r a_i}{\prod\limits_{i = 1}^{l-1} a_i}，因此不难想到我们预处理出原序列的前缀积 sum_i = \prod\limits_{j = 1}^i a_i，每次询问就是 O(1) 的了。

然后考虑模数，根据乘法逆元的定义（不会的请先移步 P3811），在模 p 意义下除以一个数等于乘以这个数的逆元，因此我们线性预处理出所有从 1 到 p 的数的逆元，对于每次询问的输出就是 \prod\limits_{i = 1}^r a_i \cdot f[\prod\limits_{i = 1}^{l-1} a_i]，其中 f[i] 表示 i 在模p意义下的乘法逆元。

AC Code

#include <bits/stdc++.h>
using namespace std;
const long long mod = 1145141;
int n, q;
long long a[1000001], sum[1000001], f[1200000];

int main(){
    scanf("%d%d", &n, &q);
    for (int i=1; i<=n; i++) scanf("%d", &a[i]);
    sum[0] = 1;
    for (int i=1; i<=n; i++) sum[i] = (sum[i - 1] * a[i]) % mod;
    f[1] = 1;
    for (int i=2; i<=mod; i++) f[i] = ((mod - mod / i) * f[mod % i]) % mod;
    int l, r;
    long long ans = 0;
    while (q--){
        scanf("%d%d", &l, &r);
        ans ^= (sum[r] * f[sum[l - 1]]) % mod;
    }
    printf("%lld\n", ans);
    return 0;
}