Description
支持以下两个操作：
- 将第 \(l\) 个数到第 \(r\) 个数 \(a_l,a_{l+1},\dots a_r\) 中的每个数 \(a_i\) 替换为 \(c^{a_i}\)。 \(c\) 是给定的常数。
- 求第 \(l\) 个数到第 \(r\) 个数的和，对 \(p\) 取模。
\(N\leq 50000,p\leq 10^8\)
Solution
首先有一道这题的弱化版：计算\(2^{2^{2^{\dots}}}\%p\) 的值。
扩展欧拉定理的板子。$$a^b\equiv \begin{cases}a^{b% \phi(p)};;;\qquad gcd(a,p)=1\a^b\qquad;\qquad;; gcd(a,p)\ne1,b<\phi(p)\a^{b%\phi(p)+\phi(p)}\quad gcd(a,p)\ne1,b\geq\phi(p)\end{cases} \qquad (mod;p)$$
首先一个结论是一个数循环取 \(phi\) ，\(O(log)\) 次之后就会变成 \(1\)。证明大概是奇数变偶数，偶数除以二。
所以这个简单题就可以不断的取 \(phi\)，当模数变成 \(1\) 时再递归回来就行了。
然后看这道省选题。
最开始还以为 \(c\) 是每次操作给的数，一直在纠结为啥操作 \(O(log)\) 次就不变了。。。
这题难点就是在每次暴力求的时候要注意很多细节。
一个就是快速幂完了之后不知道指数到底该不该再加上一个 \(\phi(p)\)。这个可以在快速幂的过程中判断，具体就是搞一个全区变量 \(flag\)，如果当前 \(ans*a\ge p\) 的话，就把这个 \(flag\) 记为 \(1\)。然后返回之后判一下，如果 \(flag\) 是 \(1\) 就加上一个 \(\phi(p)\)。
然而这样是三个 \(log\) 的，不是很过得去。我们需要消掉一个 \(log\)。
这三个 \(log\) 分别是 线段树 \(1\) 个 \(log\)，每个数暴力求 \(1\) 个 \(log\)，快速幂 \(1\) 个 \(log\)。
前面两个好像都不能优化，考虑把快速幂这个优化掉。
因为 \(p\) 最大是 \(10^8=10^4\times 10^4\)，考虑分段打表。
每次求一个数\(a^b\)的时候把 \(b\) 拆成 \(b/10000*10000+b\%10000\)，提前打出来 \(a^1,a^2\dots a^{10000}\) 和 \(a^{10000},a^{20000}\dots a^{10^8}\)这么多数。然后快速幂的时候直接查表就好了。
Code
// luogu-judger-enable-o2
#pragma GCC optimize(2)
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<cctype>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using std::min;
using std::max;
using std::swap;
using std::vector;
const int N=50005;
typedef double db;
#define re register
typedef long long ll;
#define pb(A) push_back(A)
#define pii std::pair<int,int>
#define mp(A,B) std::make_pair(A,B)
#define ls cur<<1
#define rs cur<<1|1
#define lss ls,l,mid,ql,qr
#define rss rs,mid+1,r,ql,qr
int n,m,p,c;
int phi[N],pos,flag;
pii d[40][10005],e[40][10005];
int val[N],sum[N<<2],tag[N<<2];
int getint(){
int X=0,w=0;char ch=0;
while(!isdigit(ch))w|=ch=='-',ch=getchar();
while( isdigit(ch))X=X*10+ch-48,ch=getchar();
if(w) return -X;else return X;
}
void pushup(int cur){
sum[cur]=(sum[ls]+sum[rs])%phi[0];
tag[cur]=min(tag[ls],tag[rs]);
}
void build(int cur,int l,int r){
if(l==r){sum[cur]=val[l]%phi[0];return;}int mid=l+r>>1;
build(ls,l,mid);build(rs,mid+1,r);pushup(cur);
}
int Phi(re int x){
int sq=sqrt(x),now=x;
for(int i=2;i<=x and i<=sq;i++){
if(x%i==0){
now=now/i*(i-1);
while(x%i==0) x/=i;
}
} if(x>1) now=now/x*(x-1);
return now;
}
int ksm(int a,int b,int mod){
re int ans=1;int bbb=0;
while(b){
if(b&1){
if((ll)ans*a>=(ll)mod or bbb) flag=1;
ans=(ll)ans*a%mod;
}
if((ll)a*a>=(ll)mod) bbb=1;
a=(ll)a*a%mod;b>>=1;
} if(ans>=mod) flag=1;
return ans%mod;
}
int calc(int x,int y){
re int now=x;
if(now>phi[y]) now=now%phi[y]+phi[y];
for(re int i=y;i;i--){
flag=0;int las=now;
now=(ll)e[i-1][now/10000].first*d[i-1][now%10000].first%phi[i-1];
flag=(e[i-1][las/10000].second)|(d[i-1][las%10000].second);
if(flag and i!=1) now+=phi[i-1],flag=0;
}
return now%phi[0];
}
void modify(int cur,int l,int r,int ql,int qr){
if(tag[cur]>=pos) return;
if(l==r){
++tag[cur];
sum[cur]=calc(val[l],tag[cur]);
return;
} int mid=l+r>>1;
if(ql<=mid) modify(lss);
if(mid<qr) modify(rss);
pushup(cur);
}
int query(int cur,int l,int r,int ql,int qr){
if(ql<=l and r<=qr) return sum[cur];
int mid=l+r>>1,ans=0;
if(ql<=mid) (ans+=query(lss))%=phi[0];
if(mid<qr) (ans+=query(rss))%=phi[0];
return ans;
}
signed main(){
n=getint(),m=getint(),p=getint(),c=getint();
phi[0]=p;while(p!=1) phi[++pos]=Phi(p),p=phi[pos];phi[++pos]=1;
for(int i=0;i<10000;i++){
for(int j=0;j<=pos;j++){
flag=0;
d[j][i].first=ksm(c,i,phi[j]);d[j][i].second=flag;
}
}
for(int i=0;i<=10000;i++){
for(int j=0;j<=pos;j++){
flag=0;
e[j][i].first=ksm(c,i*10000,phi[j]);e[j][i].second=flag;
}
}
for(re int i=1;i<=n;i++) val[i]=getint();
build(1,1,n);
while(m--){
if(getint()==0){
int l=getint(),r=getint();
modify(1,1,n,l,r);
} else{
int l=getint(),r=getint();
printf("%d\n",query(1,1,n,l,r)%phi[0]);
}
} return 0;
}