1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169
| #pragma GCC optimize("-Ofast") #pragma GCC optimize(3) #include <cstdio> #include <cctype> #include <cmath> #include <utility> #define ls l,mid,o<<1 #define rs mid+1,r,o<<1|1
using std::pair; using std::make_pair;
typedef long long ll;
const int maxn=(5e4+100)*2;
int a[maxn<<2],count[maxn<<2],P,c,maxlim; ll sumv[maxn<<2]; int phi[maxn],Sqrt[maxn];
char buf[1<<24],*fs; ll c_sqrt[150][maxn],c_x[150][maxn]; bool is_greater[100][maxn],is_greater_sqrt[100][maxn];
#define gc() (*fs++)
template<class T>inline T max(T a,T b){return a<b?b:a;} template<class T>inline T min(T a,T b){return a<b?a:b;}
inline int read() { char ch; while (!isdigit(ch=gc())); int x=ch^48; while (isdigit(ch=gc())) x=x*10+ch-48; return x; }
inline pair<ll,bool> qpow(ll a,ll b,ll P) { ll ans=1%P; bool gr=false; for (;b;b>>=1) { if (b&1) ans=ans*a; if (ans>=P) ans%=P,gr=true; a=a*a%P; } return make_pair(ans,gr); }
inline void CalcPower(int x,int now) { int T=Sqrt[now]=sqrt(x); c_x[now][0]=1;c_x[now][1]=c; c_sqrt[now][0]=1;pair<ll,bool> pr=qpow(c,T,x);c_sqrt[now][1]=pr.first; if (c_x[now][1]>=x) is_greater[now][1]=true,c_x[now][1]%=x; if (pr.second) is_greater_sqrt[now][1]=true; if (c_x[now][0]>=x) is_greater[now][0]=true,c_x[now][0]%=x; if (c_sqrt[now][0]>=x) is_greater_sqrt[now][0]=true,c_sqrt[now][0]%=x; for (int i=2;i<=T*2;++i) { c_x[now][i]=c_x[now][i-1]*c; c_sqrt[now][i]=c_sqrt[now][i-1]*c_sqrt[now][1]; if (c_x[now][i]>=x) is_greater[now][i]=true,c_x[now][i]%=x; if (c_sqrt[now][i]>=x) is_greater_sqrt[now][i]=true,c_sqrt[now][i]%=x; } }
inline pair<ll,bool> Fastpow(int b,int now) { ll t=c_x[now][b%Sqrt[now]]*c_sqrt[now][b/Sqrt[now]]; bool flag=is_greater[now][b%Sqrt[now]]|is_greater_sqrt[now][b/Sqrt[now]]; if (t>=phi[now]) flag=true,t%=phi[now]; return make_pair(t,flag); }
inline int Getphi(int x) { int ret=x; for (int i=2;i<=x;++i) { if (x%i==0) { while (x%i==0) x/=i; ret=ret/i*(i-1); } } if (x>1) ret=ret/x*(x-1); return ret; }
inline void Prework(int P,int i=1) { ++maxlim; if (P==1) phi[i]=1; CalcPower(phi[i]=Getphi(P),i); if (P==1) return; Prework(phi[i],i+1); }
inline ll CalcNumber(int expo,int depth,int limit) { if (depth==limit+1) return expo>phi[limit]?expo%phi[limit]+phi[limit]:expo; int t=CalcNumber(expo,depth+1,limit); pair<ll,bool> pr=Fastpow(t,depth-1); if (pr.second==1) return pr.first+phi[depth-1]; return pr.first; }
inline void Pushup(int o) { sumv[o]=sumv[o<<1]+sumv[o<<1|1]; if (sumv[o]>=P) sumv[o]-=P; }
inline void BuildSeg(int l,int r,int o) { if (l==r) return void(sumv[o]=a[l]); int mid=(l+r)>>1; BuildSeg(ls);BuildSeg(rs); Pushup(o); }
inline void Modify(int L,int R,int l,int r,int o) { if (count[o]>=maxlim) return; if (l==r) { ++count[o]; sumv[o]=CalcNumber(a[l],1,count[o])%P; return; } int mid=(l+r)>>1; if (L<=mid) Modify(L,R,ls); if (R> mid) Modify(L,R,rs); Pushup(o); count[o]=min(count[o<<1],count[o<<1|1]); }
inline int Query(int L,int R,int l,int r,int o) { if (L<=l && R>=r) return sumv[o]; int mid=(l+r)>>1; int tot=0; if (L<=mid) tot+=Query(L,R,ls); if (R> mid) tot+=Query(L,R,rs); if (tot>=P) tot-=P; return tot; }
int main() { fread(fs=buf,1,1<<24,stdin); int n=read(),m=read();phi[0]=P=read(),c=read();Sqrt[0]=sqrt(P); CalcPower(P,0); for (int i=1;i<=n;++i) a[i]=read(); Prework(P);BuildSeg(1,n,1); for (int i=1,opt,l,r;i<=m;++i) { opt=read();l=read();r=read(); if (opt) printf("%d\n",Query(l,r,1,n,1)); else Modify(l,r,1,n,1); } }
|