B3645 数列前缀和 2 - 洛谷

B3645 数列前缀和 2 - 洛谷 B 3645 数列前缀和2 题解 - lrqlrq250 的博客 - 洛谷博客

常用的 \(\LaTeX\) 公式 ![[../../../../images/Z-attachment/Pasted image 20231127160008.png]]

\(\prod \limits_{i=l}^r a_i \pmod p\) 发现等价于 \(\Huge{\frac{\prod\limits_{i=1}^{r}a_i}{\prod\limits_{i=1}^{l-1} a_i}}\)

则答案为 \(\prod\limits_{i=1}^{r}a_i \times inv[\prod\limits_{i=1}^{l-1}a_i]\) , \(inv[i]\) 为 \(i\) 在 \(\mod p\) 意义下的乘法逆元

即为 \(s[r]\times inv[s[l-1]]\) , \(\therefore\) \(ans\ \oplus={s[r]\times inv[s[l-1]]}\)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll p = 1145141;
int n, q;
ll a[1000010],inv[1200010],s[1000010];
int main()
{
    ios::sync_with_stdio(0), cin.tie(nullptr);
    s[0] = inv[1] = 1;
    cin >>n >> q;
    for (int i = 1; i <= n;i++) cin >> a[i];
    for (int i = 1; i <= n;i++) s[i] = s[i - 1] * a[i] % p;//前缀积s[i]
    for (int i = 2; i <= p; i++)//到p，不是到n!!！
        inv[i] = (p - p / i) * inv[p % i] % p;
    ll ans = 0;
    while(q--)
    {
        int l, r;
        cin >> l >> r;
        ans ^= s[r] * inv[s[l-1]] % p;
    }
    cout << ans << '\n';
}