题目
分析
首先根据扩展欧拉定理，可以知道每一个数最多取 (log) 级别次模，也就是说一个点最多修改 (log) 级别次就不会变了。
那么直接就是势能线段树的思想，直接线段树维护每一个区间的最小修改次数，然后每次暴力修改消耗势能，如果势能没了直接跳过即可。
同时这道题要使用光速幂。
代码
#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=false;
while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
#define ll long long
const int N=5e4+5,M=1e4+5,V=5e4,lim=1e4;
int mod[N],prime[N];
int Pow1[M][30],Pow2[M][30],pc[60];
bool vis[N];
int n,m,P,c,num,Ans,a[N];
int ch[N<<2][2],sum[N<<2],Min[N<<2],tot;
void Pushup(int x){
sum[x]=(1ll*sum[ch[x][0]]+sum[ch[x][1]])%P;
Min[x]=min(Min[ch[x][0]],Min[ch[x][1]]);
}
void Build(int x,int l,int r){
sum[x]=Min[x]=0;
if(l==r){sum[x]=a[l];return;}
int mid=l+r>>1;
ch[x][0]=++tot;Build(ch[x][0],l,mid);
ch[x][1]=++tot;Build(ch[x][1],mid+1,r);
Pushup(x);
}
void Build(int n){tot=1;Build(1,1,n);}
int GetPow(int x,int Mod){return 1ll*Pow2[x/lim][Mod]*Pow1[x%lim][Mod]%mod[Mod];}
int calc(int loc,int x){
int nowmi=a[loc],ret=a[loc];
for(int i=x-1;i>=0;i--){
if(nowmi==-1||nowmi>=mod[i+1]){ret=GetPow(ret%mod[i+1]+mod[i+1],i);nowmi=-1;}
else{ret=GetPow(ret,i);if(nowmi<60) nowmi=pc[nowmi];else nowmi=-1;}
}
return ret;
}
void Update(int x,int l,int r,int ql,int qr){
if(Min[x]>=num) return;
if(ql==qr){
++Min[x];
sum[x]=calc(ql,Min[x]);
return;
}
int mid=ql+qr>>1;
if(l<=mid) Update(ch[x][0],l,r,ql,mid);
if(r>mid) Update(ch[x][1],l,r,mid+1,qr);
Pushup(x);
}
void Update(int l,int r){
Update(1,l,r,1,n);
}
int Query(int x,int l,int r,int ql,int qr){
if(l<=ql&&qr<=r) return sum[x];
int mid=ql+qr>>1,ret=0;
if(l<=mid) ret=(1ll*ret+Query(ch[x][0],l,r,ql,mid))%P;
if(r>mid) ret=(1ll*ret+Query(ch[x][1],l,r,mid+1,qr))%P;
return ret;
}
int Query(int l,int r){
return Query(1,l,r,1,n);
}
int GetPhi(int x){
int ret=x;
for(int i=1;prime[i]*prime[i]<=x;i++){
if(x%prime[i]) continue;
ret=ret-ret/prime[i];
while(x%prime[i]==0) x/=prime[i];
}
if(x>1) ret=ret-ret/x;
return ret;
}
int QuickPow(int x,int y,int p){
int res=1;
for(;y;y>>=1,x=1ll*x*x%p) if(y&1) res=1ll*res*x%p;
return res;
}
inline void GetPrimes(int n){
int cnt=0;
for(int i=2;i<n;i++){
if(!vis[i]) prime[++cnt]=i;
for(int j=1;j<=cnt&&prime[j]*i<n;j++){
vis[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
return ;
}
void Init(int n){
mod[0]=P;
num=0;
while(mod[num]!=1) num++,mod[num]=GetPhi(mod[num-1]);
mod[++num]=1;
for(int i=0;i<=lim;i++) for(int j=0;j<=num;j++) Pow1[i][j]=QuickPow(c,i,mod[j]);
for(int i=0;i<=lim;i++) for(int j=0;j<=num;j++) Pow2[i][j]=QuickPow(QuickPow(c,lim,mod[j]),i,mod[j]);
pc[0]=1;
int flag=1e5;
for(int i=1;i<60;i++){
if(pc[i-1]==-1) pc[i]=-1;
if(1ll*pc[i-1]*c<=1e9) pc[i]=pc[i-1]*c;
else pc[i]=-1,flag=min(flag,i);
}
return ;
}
signed main(){
int op,l,r;
read(n),read(m),read(P),read(c);
for(int i=1;i<=n;i++) read(a[i]);
GetPrimes(V);
Init(V);
Build(n);
for(int i=1;i<=m;i++){
read(op),read(l),read(r);
if(op==0) Update(l,r);
else Ans=Query(l,r),write(Ans),putchar('
');
}
return 0;
}