题意

给出一个序列a，模数p和一个常数c，要求资瓷两个操作： 0 l r表示把l<=i<=r的a[i]变为 ca[i] 1 l r表示查询a[l..r]的和。 n,m<=50000,a[i],c,p<=10^9

分析

首先这题要用到欧拉定理EXT： 当x>=φ(p)时有cx≡cxmodφ(p)+φ(p) 因为注意到式子右边的次方上面又是一个相同形式的式子，我们可以用同样的方式递归处理。 那么我们就可以预处理出phi[i]表示p取i次phi后的值。因为一个数最多取O(logn)次phi后就会变为1，所以i最大为logp.然后最后还要多加一个1. 还有一个结论就是一个数在做常数次修改操作后就会变为不动点。 所以我们可以每次找到未被修改完的区间，然后每次暴力修改。 这样复杂度大概是O(nlog3n)，在bzoj上能过。

这里还可以优化掉快速幂的那一个log，就是把一个数分成大于 216和小于216的部分 ，然后分别预处理出来，就可以O(1)做快速幂了。

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; typedef long long LL; const int N=50005; const int M=35; int n,m,phi[M],c,p1,a[N],table[32][1<<16][2]; struct tree{int s,tms;}t[N*5]; bool flag[32][1<<16][2]; int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int ksm(int x,int y,int MOD,bool &flag) { int ans=1;flag=0; while (y) { if (y&1) flag|=((LL)ans*x>=MOD),ans=(LL)ans*x%MOD; flag|=((LL)x*x>=MOD&&y>1);x=(LL)x*x%MOD;y>>=1; } return ans; } int bksm(int x,int y,bool &w) { int p=x&((1<<16)-1),q=x>>16; w=flag[y][p][0]|flag[y][q][1]|((LL)table[y][p][0]*table[y][q][1]>=phi[y]); return (LL)table[y][p][0]*table[y][q][1]%phi[y]; } int calc(int x,int p) { int ret=x;bool flag; if (ret>=phi[p]) ret=ret%phi[p]+phi[p]; while (p--) { x=ret; ret=bksm(x,p,flag); if (flag) ret+=phi[p]; } return ret%phi[0]; } int get_phi(int n) { int w=n,tmp=n; for (int i=2;i*i<=n;i++) if (tmp%i==0) { w=w/i*(i-1); while (tmp%i==0) tmp/=i; } if (tmp>1) w=w/tmp*(tmp-1); return w; } void updata(int d) { t[d].s=(t[d*2].s+t[d*2+1].s)%phi[0]; t[d].tms=min(t[d*2].tms,t[d*2+1].tms); } void build(int d,int l,int r) { if (l==r) { t[d].s=a[l]%phi[0]; return; } int mid=(l+r)/2; build(d*2,l,mid);build(d*2+1,mid+1,r); updata(d); } void modify(int d,int l,int r,int x,int y) { if (x>y||t[d].tms==p1) return; if (l==r) { t[d].tms++; t[d].s=calc(a[l],t[d].tms); return; } int mid=(l+r)/2; modify(d*2,l,mid,x,min(y,mid)); modify(d*2+1,mid+1,r,max(x,mid+1),y); updata(d); } int query(int d,int l,int r,int x,int y) { if (x>y) return 0; if (l==x&&r==y) return t[d].s; int mid=(l+r)/2; return (query(d*2,l,mid,x,min(y,mid))+query(d*2+1,mid+1,r,max(x,mid+1),y))%phi[0]; } void prework() { for (int i=0;i<=p1;i++) { table[i][0][0]=table[i][0][1]=1; if (phi[i]==1) flag[i][0][0]=flag[i][0][1]=1; int tmp=ksm(c,1<<16,phi[i],flag[i][1][1]),c1=ksm(c,1,phi[i],flag[i][1][0]); table[i][1][0]=c1;table[i][1][1]=tmp; for (int j=2;j<(1<<16);j++) { flag[i][j][0]=flag[i][j-1][0]|((LL)table[i][j-1][0]*c>=phi[i]); table[i][j][0]=(LL)table[i][j-1][0]*c%phi[i]; flag[i][j][1]=flag[i][j-1][1]|((LL)table[i][j-1][1]*tmp>=phi[i]); table[i][j][1]=(LL)table[i][j-1][1]*tmp%phi[i]; } } } int main() { n=read();m=read();phi[0]=read();c=read(); p1=0; while (phi[p1]>1) p1++,phi[p1]=get_phi(phi[p1-1]); phi[++p1]=1; prework(); for (int i=1;i<=n;i++) a[i]=read(); build(1,1,n); while (m--) { int op=read(),l=read(),r=read(); if (!op) modify(1,1,n,l,r); else printf("%d\n",query(1,1,n,l,r)); } return 0; }