如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY-NC-SA 4.0 （除特别声明或转载文章外）
操作1：区间加
这不是一个树状数组的事吗，区间加，单点查询 ，线段树是什么，树状数组是真的好写还不卡常。什么，你不会，这边请。—>传送门
操作2：询问
给定 $l,r,p$ 查询：
\[a_{l}^{a_{l+1}^{\cdots^{a_r}}} \operatorname{mod} p\]考虑欧拉定理降幂，我们会发现 $\gcd(a_l,p)\ne 1$。
所以我们考虑用扩展欧拉定理：—> 传送门
\[a^b\equiv\begin{cases}a^{b\operatorname{mod}\varphi(p)}&b<\varphi(p)\\a^{b\operatorname{mod}\varphi(p)+\varphi(p)}&b\ge\varphi(p)\end{cases}(\operatorname{mod}p)\]由于本题不是模板，证明就不放了。
那么显然，本题就变成了递归的过程，在递归时要注意边界的判断：
- $l=r$ 时返回该位上的值；
- $p=1$ 时返回 $0$。
我们会注意到我们不能知道我们的指数是否取过模，所以考虑用结构体存储。
时间复杂度
$\mathrm {O(m\log^2p)}$，认为 $\mathrm{O(\log p),O(\log n),O(\log a_i)}$ 同级。
每次询问时的递归，$\varphi(p)$ 只需要递归 $\log p$ 次就会变成 $1$，而每次递归时需要树状数组单点查询$\mathrm{O(\log n)}$，快速幂$\mathrm{O(\log a_i)}$
代码
大体思路就这些，接下来就是实现了：
#include<cstdio>
int n,m;
long long c[500010];
void update(int i,int const &x){
for(;i<=n;i+=(i&-i))c[i]+=x;
}
long long query(int i,long long res=0){
for(;i;i-=(i&-i))res+=c[i];
return res;
}
struct node{
long long v;
bool a;
node(long long const &_v,bool const &_a):v(_v),a(_a){}
};
node pow(long long x,long long y,int const &p){
node res(1,false);
if(x>p) x%=p,res.a=true;
while(y){
if(y&1){
res.v*=x;
if(res.v>p){
res.a=true;
res.v%=p;
}
}
x=x*x;
if(x>p){
res.a=true;
x%=p;
}
y>>=1;
}
return res;
}
int phi[20000005],p[1271000],cnt;
char np[20000005];
node query(int const &l,int const &r,int const &p){
if(p==1) return node(0ll,true);
long long t=query(l);
if(t==1) return node(1ll,false);
if(l==r){
if(t>=p) return node(t%p,true);
else return node(t,false);
}
node k=query(l+1,r,phi[p]);
if(k.a) k.v+=phi[p];
return pow(t,k.v,p);
}
int main(){
phi[1]=1;
for(int i=2;i<=20000000;i++){
if(!np[i]) p[++cnt]=i,phi[i]=i-1;
for(int j=1;j<=cnt&&i*p[j]<=20000000;j++){
np[i*p[j]]=1;
if(i%p[j]==0){
phi[i*p[j]]=phi[i]*p[j];
break;
}
phi[i*p[j]]=phi[i]*(p[j]-1);
}
}
scanf("%d%d",&n,&m);
for(int i=1,k=0,x;i<=n;i++){
scanf("%d",&x);
update(i,x-k);
k=x;
}
while(m--){
int op,l,r,x;
scanf("%d%d%d%d",&op,&l,&r,&x);
if(op==1){
update(l,x);
update(r+1,-x);
}else{
printf("%lld\n",query(l,r,x).v);
}
}
return 0;
}