传送门

相逢是问候

题目大意

对于一个可修改序列:
区间修改将[l,r]间的数ai修改为c^ai
区间查询求[l,r]区间数的和 mod p

前置知识

P5091扩展欧拉定理

当b≥φ(p),有：a^{b} ≡ a^(b mod φ(p) + φ(p))(mod p)

P4139上帝与集合的正确用法

分析

我们发现我们可以通过预处理的方式降低修改的复杂度。
但 p ≤ 10^8，所以我们选择将p拆成两个四位数的组合。（根据模运算满足加法和乘法）
这时时间复杂度为O(nlog^2n)

实现

int phi(int p){
	int ans = 1;int num = 1;
	for(int i = 2;i*i <= p;i++){
		if(p%i == 0){
			num = i - 1;
			p /= i;
			while(p%i == 0){
				num *= i;
				p /= i;
			}
			ans *= num;
		}
	}
	if(p != 1){
		ans *= (p - 1);
	}
	return ans;
}

我们用以上函数求出p,φ(p),φ(φ(p)) ....
每一个都是O(√n)，总体复杂度 < O(log n * √n)

注意：

1.在存储p,φ(p),φ(φ(p)) .... 是要在序列最后在加入一个1，保证对ai = 0的特殊情况的正确处理。
2.计算是可以计算p,φ(p),φ(φ(p)) .... 与c是否互质，用于判断是使用欧拉定理还是拓展欧拉定理（非必须）

我的代码

#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
#define maxn 50010
int phi(int p){
	int ans = 1;int num = 1;
	for(int i = 2;i*i <= p;i++){
		if(p%i == 0){
			num = i - 1;
			p /= i;
			while(p%i == 0){
				num *= i;
				p /= i;
			}
			ans *= num;
		}
	}
	if(p != 1){
		ans *= (p - 1);
	}
	return ans;
}
int n,m,p,c;
int a[maxn];
int gcd(int x,int y){
	if(y == 0){
		return x;
	}
	return gcd(y,x%y);
}

int ph[maxn],pcnt;
int g[maxn];
int s1[10010][31],s2[10010][31];
bool tg1[10010][31],tg2[10010][31];
int f[maxn][31][31];
bool b[maxn][31][31];
void pre(){
	int x = p;ph[0] = p;
	while(x != 1){
		x = phi(x);ph[++pcnt] = x; 
	}
	ph[++pcnt] = 1;
	for(int i = 0;i <= pcnt;i++){
		g[i] = gcd(c,ph[i]);
	}
	for(int i = 0;i <= pcnt;i++){
		s2[0][i] = 1;
		for(int j = 1;j <= 10000;j++){
			s2[j][i] = s2[j - 1][i]*c;
			if(s2[j][i] >= ph[i]){
				s2[j][i] = s2[j][i]%ph[i];
				tg2[j][i] = 1;
			}
			tg2[j][i] |= tg2[j - 1][i]; 
		}
	}
	for(int i = 0;i <= pcnt;i++){
		s1[0][i] = 1;
		tg1[1][i] = tg2[10000][i];
		for(int j = 1;j <= 10000;j++){
			s1[j][i] = s1[j - 1][i] * s2[10000][i];
			if(s1[j][i] >= ph[i]){
				s1[j][i] = s1[j][i]%ph[i];
				tg1[j][i] = 1;
			}
			tg1[j][i] |= tg1[j - 1][i];
		}
	}
	for(int i = 1;i <= n;i++){
		for(int k = 0;k <= pcnt;k++){
			f[i][0][k] = a[i]%ph[k];
			if(a[i] >= ph[k]){
				b[i][0][k] = 1;
			}
		}
		for(int j = 1;j <= pcnt;j++){
			f[i][j][pcnt] = 0;
			for(int k = 0;k < pcnt;k++){
				f[i][j][k] = s1[f[i][j - 1][k + 1]/10000][k] *s2[f[i][j - 1][k + 1]%10000][k];
				b[i][j][k] = tg1[f[i][j - 1][k + 1]/10000][k] || tg2[f[i][j - 1][k + 1]%10000][k];
				if(f[i][j][k] >= ph[k]){
					f[i][j][k] = f[i][j][k] % ph[k];
					b[i][j][k] = 1;
				}
				if(b[i][j - 1][k +1]){
					f[i][j][k] = (f[i][j][k] * s1[ph[k + 1]/10000][k] )% ph[k] *s2[ph[k + 1]%10000][k];
					if(f[i][j][k] >= ph[k]){
						f[i][j][k] = f[i][j][k] % ph[k];
						b[i][j][k] = 1; 
					}
					b[i][j][k] = (b[i][j][k]||(tg1[ph[k + 1]/10000][k] || tg2[ph[k + 1]%10000][k]));
				}
			}
		} 
	}
	return ;
}
struct TREE{
	int w[maxn*4],tag[maxn*4];
	void pushup(int id){
		w[id] = w[(id<<1)] + w[((id<<1) + 1)];
		tag[id] = min(tag[(id<<1)],tag[((id<<1) + 1)]);
		return ;
	}
	void build(int L,int R,int id){
		if(L == R){
			w[id] = a[L];
			tag[id] = 0;
			return ;
		}
		int mid = (L + R)>>1;
		build(L,mid,(id<<1));
		build(mid + 1,R,((id<<1) + 1));
		pushup(id);
		return ;
	}
	void cov(int l,int r,int L ,int R,int id){
		if(tag[id] >= pcnt){
			return ;
		}
		if(l > R|| r < L){
			return ;
		}
		if(l == r){
			tag[id]++;
			w[id] = (f[l][tag[id]][0])%p;
			return ;
		} 
		int mid = (l + r)>>1;
		if(tag[(id<<1)] < pcnt){
			cov(l,mid,L,R,(id<<1));
		}
		if(tag[((id<<1) + 1)] < pcnt){
			cov(mid + 1,r,L,R,((id<<1) + 1));
		}
		pushup(id);
		return ;
	}
	int ask(int l,int r,int L,int R,int id){
		if(l >= L && R >= r){
			return w[id]%p;
		}
		int mid = (l + r)>>1;
		int ans = 0;
		if(L <= mid){
			ans += ask(l,mid,L,R,(id<<1));
		}
		if(R > mid){
			ans += ask(mid + 1,r,L,R,(id<<1) +1);	  
		}
		return ans%p;
	} 
}tr;

signed main(){
	scanf("%lld%lld%lld%lld",&n,&m,&p,&c);
	for(int i = 1;i <= n;i++){
		scanf("%lld",&a[i]);
	}
	pre();
	tr.build(1,n,1);
	int tp,l,r; 
	for(int i = 1;i <= m;i++){
		scanf("%lld%lld%lld",&tp,&l,&r);
		if(tp == 0){
			tr.cov(1,n,l,r,1);
		}else{
			printf("%lld\n",tr.ask(1,n,l,r,1));
		}
	}
	return 0;
}