提交记录

Code:

#include <bits/stdc++.h>
#define ls (u << 1)
#define rs (u << 1 | 1)
using namespace std;
using LL = long long;

constexpr const int N = 5e4 + 3;
int cnt[N << 2], phi[N], idx = 0, a[N][60], c;
LL T[N << 2];

int read() {
	int res = 0;
	char ch = getchar_unlocked();
	for(; '0' > ch || ch > '9'; ch = getchar_unlocked());
	for(; '0' <= ch && ch <= '9'; ch = getchar_unlocked())
		res = res * 10 + ch - '0';
	return res;
}

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

int Mod(LL x, const int mod)
{ return x >= mod? x % mod + mod: x; }

int qpow(int x, int y, const int mod) {
	int res = 1;
	for(; y; x = Mod((LL)x * x, mod), y >>= 1)
		if(y & 1)
			res = Mod((LL)res * x, mod);
	return res;
}

int calc(int x, int k, int id) {
	if(phi[id] == 1)
		return c? 1: 0;
	else if(id == k - 1)
		return qpow(c, x, phi[id]);
	else
		return qpow(c, calc(x, k, id + 1), phi[id]);
}

void pushUp(int u) {
	T[u] = T[ls] + T[rs];
	cnt[u] = min(cnt[ls], cnt[rs]);
}

void build(int u, int L, int R) {
	if(L == R) {
		T[u] = a[L][0];
		return;
	}
	int M = (L + R) >> 1;
	build(ls, L, M);
	build(rs, M + 1, R);
	T[u] = T[ls] + T[rs];
}

void chg(int u, int L, int R, int x, int y) {
	if(cnt[u] >= idx + 1)
		return;
	if(L == R) {
		++cnt[u];
		T[u] = a[L][min(cnt[u], idx + 1)];
		return;
	}
	int M = (L + R) >> 1;
	if(x <= M)
		chg(ls, L, M, x, y);
	if(y > M)
		chg(rs, M + 1, R, x, y);
	pushUp(u);
}

LL ask(int u, int L, int R, int x, int y) {
	if (x <= L && R <= y)
		return T[u];
	int M = (L + R) >> 1;
	LL ans = 0;
	if(x <= M)
		ans = ask(ls, L, M, x, y);
	if(y > M)
		ans += ask(rs, M + 1, R, x, y);
	return ans;
}

int main() {
	int n = read(), m = read(), P = read(); c = read();
	for(phi[0] = P; phi[idx] > 1; ++idx)
		phi[idx + 1] = calc(phi[idx]);
	for(int i = 1; i <= n; ++i) {
		a[i][0] = read();
		for(int j = 1; j <= idx + 1; ++j)
			a[i][j] = calc(a[i][0], j, 0);
	}
	build(1, 1, n);
	for(int op, L, R; m--; ) {
		op = read(); L = read(); R = read();
		if(op)
			printf("%lld\n", ask(1, 1, n, L, R) % P);
		else
			chg(1, 1, n, L, R);
	}
	return 0;
}