A1776 数列前缀和 2

#include <bits/stdc++.h>
using namespace std;

// 数列前缀和 2：区间乘积 mod p，单次询问 O(1)。
//
// p = 1145141 是质数，且 1 <= a_i < p，所以每个 a_i 在模 p 意义下都非零、
// 都可逆。记 pre[i] = a_1 * a_2 * ... * a_i mod p（pre[0] = 1），
// 则区间乘积 prod(l..r) = pre[r] * pre[l-1]^{-1} mod p。
//
// 逆元不必一个个用快速幂求：先用一次费马小定理算出 inv[n]，
// 再由 pre[i] = pre[i-1] * a[i] 倒推 inv[i-1] = inv[i] * a[i] mod p，
// 整个预处理是 O(n + log p)。
const int MOD = 1145141;

long long qpow(long long a, long long b) {
    long long r = 1;
    while (b > 0) {
        if (b & 1) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<int> a(n + 1), pre(n + 1), inv(n + 1);
    pre[0] = 1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = (long long)pre[i - 1] * a[i] % MOD;
    }

    // 只做一次快速幂，其余逆元倒着推
    inv[n] = (int)qpow(pre[n], MOD - 2);
    for (int i = n; i >= 1; i--) {
        inv[i - 1] = (long long)inv[i] * a[i] % MOD;
    }

    int ans = 0;
    while (q--) {
        int l, r;
        cin >> l >> r;
        int v = (long long)pre[r] * inv[l - 1] % MOD;
        ans ^= v;
    }

    cout << ans << "\n";
    return 0;
}