蒟蒻的沙雕代码
线段树+欧拉函数降幂
只有60分
1个TLE
3个WA
为什么会WA？？？
空间开大了也没用

#include<bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;
int n,m,q;
const int maxn=1000001;
struct linetree{
	int l,r;
	ll sum,lazy;
}t[4*maxn];
int a[maxn];
int ls(int x){
	return 2*x;
}
int rs(int x){
	return 2*x+1;
}
void make(int p,int l,int r){
	t[p].l=l;
	t[p].r=r;
	if(l==r){
		t[p].sum=a[l];
		return;
	}
	int mid=(l+r)/2;
	make(ls(p),l,mid);
	make(rs(p),mid+1,r);
	t[p].sum=t[ls(p)].sum+t[rs(p)].sum;
}
void spread(int p){
    if(t[p].lazy){
        t[ls(p)].sum+=t[p].lazy*(t[ls(p)].r-t[ls(p)].l+1);
        t[rs(p)].sum+=t[p].lazy*(t[rs(p)].r-t[rs(p)].l+1);
        t[ls(p)].lazy+=t[p].lazy;
        t[rs(p)].lazy+=t[p].lazy;
        t[p].lazy=0;
    }
}
void add(int p,int x,int y,int z){
    if(x<=t[p].l&&y>=t[p].r){
        t[p].sum+=1ll*z*(t[p].r-t[p].l+1);
        t[p].lazy+=z;
        return;
    }
    spread(p);
    int mid=(t[p].l+t[p].r)/2;
    if(x<=mid) add(ls(p),x,y,z);
    if(y>mid) add(rs(p),x,y,z);
    t[p].sum=t[ls(p)].sum+t[rs(p)].sum;   
}
ll query(int p,int x,int y){
	if(x<=t[p].l&&y>=t[p].r) return t[p].sum;
	spread(p);
	int mid=(t[p].l+t[p].r)/2;
	ll s=0;
	if(x<=mid) s+=query(ls(p),x,y);
    if(y>mid) s+=query(rs(p),x,y);
    //cout<<t[p].l<<"  "<<t[p].r<<":"<<s<<endl;
    return s;
}
map<int,int>ph;
int phi(int x){
	int i,ans=x;
	for(i=2;i*i<=x;i++){
		if(x%i==0) ans-=ans/i;
		while(x%i==0) x/=i;
		//cout<<ans<<endl;
	}
	if(x>1) ans-=ans/x;
	return ans;
}
int qmi(int b,int p,int k){
	int ans=1;
	bool f=false;
	while(p){
		if(p&1){
			ans=ans*b;
			if(ans>=k) f=true;
			ans%=k;
		}
		b*=b;
		if(b>=k) f=true;
		b%=k; 
		p>>=1;
	}
	if(f) ans+=k;
	return ans;
}
int getans(int l,int r,int mod){
	if(l==r+1||mod==1) return 1;
	else return qmi(query(1,l,l),getans(l+1,r,ph[mod]),mod);
}
signed main(){
	cin>>n>>q;
	int l,r,opt,num;
	for(int i=1;i<=n;i++) cin>>a[i];
	make(1,1,n);
	while(q--){
		cin>>opt>>l>>r>>num;
		if(opt==1){
			add(1,l,r,num);
		}
		else{
			ph.clear();
			int num1=num;
			while(num1!=1){
				ph[num1]=phi(num1);
				num1=ph[num1];
				//cout<<num1<<endl;
			}
			ph[num1]=1;
			cout<<getans(l,r,num)%num<<"\n";
		}
	}
}