记录编号	608010	评测结果	AAAAAAAAAA
题目名称	2511.学姐的巧克力盒	最终得分	100
用户昵称	淮淮清子	是否通过	通过
代码语言	C++	运行时间	8.894 s
提交时间	2025-10-22 15:02:58	内存使用	30.17 MiB

#include <iostream>
#include <cstdio>
using namespace std;

#define ll long long
#define ls (p << 1)
#define rs (p << 1 | 1)
const int MAXN = 1e6 + 5;

int n, m, k, p1, p2, phi;
int a[MAXN];

struct Tree {
    int l, r;
    ll prod[2];
} t[MAXN << 2];

void read(int &x) {
    x = 0; int f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + ch - '0'; ch = getchar(); }
    x *= f;
}

void pushup(int p) {
    if (p1) t[p].prod[0] = t[ls].prod[0] * t[rs].prod[0] % p1;
    if (p2) t[p].prod[1] = t[ls].prod[1] * t[rs].prod[1] % phi;
}

void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if (l == r) {
        if (p1) t[p].prod[0] = a[l] % p1;
        if (p2) t[p].prod[1] = a[l] % phi;
        return;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(p);
}

ll query(int p, int L, int R, int o) {
    if (t[p].r < L || t[p].l > R) return 1;
    if (L <= t[p].l && t[p].r <= R) return t[p].prod[o];
    return query(ls, L, R, o) * query(rs, L, R, o) % (o == 0 ? p1 : phi);
}

int euler(int x) {
    int res = x;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1) res = res / x * (x - 1);
    return res;
}

ll qpow(ll a, ll b, ll mod) {
    ll res = 1;
    a %= mod;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main() {
    freopen("chocolatebox.in", "r", stdin);
    freopen("chocolatebox.out", "w", stdout);

    read(n), read(m), read(k), read(p1), read(p2);
    for (int i = 1; i <= n; i++) read(a[i]);

    if (p2) phi = euler(p2);

    build(1, 1, n);

    while (m--) {
        int op, l, r;
        read(op), read(l), read(r);
        if (op == 1 && p1) {
            cout << query(1, l, r, 0) << '\n';
        } else if (op == 2 && p2) {
            ll e = query(1, l, r, 1);
            cout << qpow(k, e, p2) << '\n';
        }
    }

    return 0;
}