由扩展欧拉定理，a^(a^(a^(……^x)))%p中x作为指数的模数应该是φ(φ(φ(φ(……p))))，而p取log次φ就会变为1，也即每个位置一旦被修改一定次数后就会变为定值。线段树维护区间剩余修改次数的最大值，暴力修改即可。
可以预处理出每个位置进行k次操作后的值。直接计算是log^3的，会被卡常。考虑类似bsgs的分块，将指数拆成<10000和10000m两部分，预处理后即可O(1)查询，避免每次快速幂。
注意当指数<φ(p)不能加φ(p)。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define N 50010 int n,m,p,c,phi[30],a[N][30][30],p1[10010][30],p2[10010][30],t; bool flag[N][30][30],flag1[10010][30],flag2[10010][30],f; int L[N<<2],R[N<<2],cnt[N<<2],sum[N<<2]; int ksm(int k,int p) { int x=k/10000,y=k%10000; f=flag2[x][p]||flag1[y][p]||1ll*p2[x][p]*p1[y][p]>=phi[p]; return 1ll*p2[x][p]*p1[y][p]%phi[p]; } void up(int k) { cnt[k]=min(cnt[k<<1],cnt[k<<1|1]); sum[k]=(sum[k<<1]+sum[k<<1|1])%phi[0]; } void build(int k,int l,int r) { L[k]=l,R[k]=r; if (l==r) {cnt[k]=0,sum[k]=a[l][0][0];return;} int mid=l+r>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); up(k); } void modify(int k,int l,int r) { if (cnt[k]==t) return; if (L[k]==R[k]) {cnt[k]++,sum[k]=a[l][cnt[k]][0];return;} int mid=L[k]+R[k]>>1; if (r<=mid) modify(k<<1,l,r); else if (l>mid) modify(k<<1|1,l,r); else modify(k<<1,l,mid),modify(k<<1|1,mid+1,r); up(k); } int query(int k,int l,int r) { if (L[k]==l&&R[k]==r) return sum[k]; int mid=L[k]+R[k]>>1; if (r<=mid) return query(k<<1,l,r); else if (l>mid) return query(k<<1|1,l,r); else return (query(k<<1,l,mid)+query(k<<1|1,mid+1,r))%phi[0]; } int main() { #ifndef ONLINE_JUDGE freopen("bzoj4869.in","r",stdin); freopen("bzoj4869.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif n=read(),m=read(),p=read(),c=read(); phi[0]=p; while (p>1) { phi[++t]=1; for (int i=2;i*i<=p;i++) if (p%i==0) { phi[t]*=i-1;p/=i; while (p%i==0) phi[t]*=i,p/=i; } if (p>1) phi[t]*=p-1; p=phi[t]; } phi[++t]=1; for (int i=0;i<=t;i++) { p1[0][i]=1%phi[i],flag1[0][i]=1>=phi[i]; for (int j=1;j<=10000;j++) flag1[j][i]=flag1[j-1][i]||1ll*p1[j-1][i]*c>=phi[i],p1[j][i]=1ll*p1[j-1][i]*c%phi[i]; p2[0][i]=1%phi[i],flag1[1][i]=1>=phi[i]; for (int j=1;j<=10000;j++) flag2[j][i]=flag2[j-1][i]||1ll*p2[j-1][i]*p1[10000][i]>=phi[i],p2[j][i]=1ll*p2[j-1][i]*p1[10000][i]%phi[i]; } for (int i=1;i<=n;i++) { a[i][0][0]=read();for (int j=1;j<=t;j++) flag[i][0][j]=a[i][0][0]>=phi[j],a[i][0][j]=a[i][0][0]%phi[j]; for (int j=1;j<=t;j++) for (int k=0;k<=t-j;k++) { f=0; a[i][j][k]=ksm(a[i][j-1][k+1]+flag[i][j-1][k+1]*phi[k+1],k); flag[i][j][k]=f|flag[i][j-1][k+1]; } } build(1,1,n); while (m--) { int op=read(),l=read(),r=read(); if (op==0) modify(1,l,r); else printf("%d ",query(1,l,r)); } return 0; }