4869: [Shoi2017]相逢是问候

题意：一个序列，支持区间\(a_i \leftarrow c^{a_i}\)，区间求和。在模p意义下。

类似于开根操作，每次取phi在log次后就不变了。

不互质怎么办？ 我才知道，

不要求互质，只要求\(x \ge \varphi(p)\)

然后就很好做了...线段树维护每个点的操作次数和和，修改的时候每个点算一下，不变的区间不再更新。

有一个问题，必须把\(\varphi(1)=1\)也加进去。我想了好久好久...因为

如果这个序列的数是0，再加一层之后和之前并不是不变的！

然后需要给快速幂加点特技...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

#define mid ((l+r)>>1)

#define lc x<<1

#define rc x<<1|1

#define lson lc, l, mid

#define rson rc, mid+1, r

const int N = 5e4+5;

inline int read() {

	char c=getchar(); int x=0,f=1;

	while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}

	while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}

	return x*f;

}

int n, Q, p, c, a[N], op, l, r, phi[100], m, mo;

int Phi(int n) {

	int m = sqrt(n), ans = n;

	for(int i=2; i<=m; i++) if(n % i == 0) {

		ans = ans / i * (i-1);

		while(n % i == 0) n /= i;

	}

	if(n > 1) ans = ans / n * (n-1);

	return ans;

}

int Pow(ll a, int b, ll mo, bool &flag) {

	ll ans = 1;

	bool big = 0;

	for(; b; b>>=1) {

		if(b&1) {

			ans = ans * a;

			flag |= big | (ans >= mo);

			ans %= mo;

		}

		a = a * a; if(a >= mo) big = 1, a %= mo;

	}

	return ans;

}

int cal(int x, int ci) {

	if(x >= phi[ci]) x = x % phi[ci] + phi[ci];// flag = 1;

	for(int i=ci-1; i>=0; i--) {

		bool flag = 0;

		x = Pow(c, x, phi[i], flag);

		if(flag) x += phi[i];

	}

	return x % phi[0];

}

namespace S {

	struct meow{int sum, ci;} t[N<<2];

	void merge(int x) {

		t[x].sum = (t[lc].sum + t[rc].sum) %mo;

		t[x].ci = min(t[lc].ci, t[rc].ci);

	}

	void build(int x, int l, int r) {

		if(l == r) t[x].sum = a[l];

		else {

			build(lson);

			build(rson);

			merge(x);

		}

	}

	void cat(int x, int l, int r, int ql, int qr) {

		if(t[x].ci >= m) return;

		if(l == r) t[x].ci++, t[x].sum = cal(a[l], t[x].ci);

		else {

			if(ql <= mid) cat(lson, ql, qr);

			if(mid < qr)  cat(rson, ql, qr);

			merge(x);

		}

	}

	int que(int x, int l, int r, int ql, int qr) {

		if(ql<=l && r<=qr) return t[x].sum;

		else {

			int ans = 0;

			if(ql <= mid) ans = (ans + que(lson, ql, qr)) %mo;

			if(mid < qr)  ans = (ans + que(rson, ql, qr)) %mo;

			return ans;

		}

	}

}

int main() {

	freopen("in", "r", stdin);

	n=read(); Q=read(); p=read(); c=read();

	for(int i=1; i<=n; i++) a[i] = read();

	mo = phi[0] = p;

	while(p != 1) phi[++m] = p = Phi(p);

	phi[++m] = 1;

	S::build(1, 1, n);

	for(int i=1; i<=Q; i++) {

		op=read(); l=read(); r=read();

		if(!op) S::cat(1, 1, n, l, r);

		else printf("%d\n", S::que(1, 1, n, l, r));

	}

}