提交记录

#include<iostream>
#include<cstdio>
#define int long long
#define MAXN 500005
using namespace std;
int a[MAXN],c[MAXN],n,m;
struct Ans{int a;bool b;};

inline int read(){
	int x=0;char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x;
}

inline int lowbit(int x){return x&(-x);}
inline void update(int i,int k){
	while(i<=n){
		c[i]+=k;
		i+=lowbit(i);
	}
}
inline int query(int i){
	int sum=0;
	while(i>0){
		sum+=c[i];
		i-=lowbit(i);
	}
	return sum;
}

const int MAXP=100000008;
int prime[MAXP],cnt,phi[MAXP];bool notprime[MAXP];
void Euler(int n){
	phi[1]=1;
	for(int i=2;i<=n;++i){
		if(!notprime[i]) prime[++cnt]=i,phi[i]=i-1;
		for(int j=1;j<=cnt&&i*prime[j]<=n;++j){
			notprime[i*prime[j]]=true;
			if(i%prime[j]==0){
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
	}
	return;
}
int gcd(int a,int b){while(b^=a^=b^=a%=b);return a;}

Ans pow(int a,int b,int p){
	Ans ans;ans.a=1;ans.b=true;int base=a,i;
	for(i=1;i<=b;i<<=1){
		if(b&i)
			if((ans.a=ans.a*base)>=p)
				{ans.b=false;break;}
		if((base=base*base)>=p) break;
	}
	for(;i<=b;i<<=1)
		if(b&i)
			{ans.b=false;break;}
	ans.a=1;base=a%p;
	for(int i=1;i<=b;i<<=1){
		if(b&i)
			ans.a=ans.a*base%p;
		base=base*base%p;
	}
	return ans;
}
Ans f(int l,int r,int p){
	a[l]=query(l);
	Ans ans,x;
	if(p==1){ans.a=0;ans.b=false;return ans;}
	if(l==r){ans.a=a[l]%p;ans.b=(a[l]<p);return ans;}
	x=f(l+1,r,phi[p]);
	if(gcd(a[l],p)==1) return pow(a[l],x.a,p);
	if(x.b) return pow(a[l],x.a,p);
	return pow(a[l],x.a+phi[p],p);
}

signed main(){
	n=read();m=read();
	Euler(20000001);
	for(int i=1;i<=n;++i) a[i]=read();
	for(int i=n;i>=1;--i) a[i]=a[i]-a[i-1];
	for(int i=1;i<=n;++i) update(i,a[i]);
	for(int i=1,a,b,c,d;i<=m;++i){
		a=read();b=read();c=read();d=read();
		if(a==1) {update(b,d);update(c+1,-d);}
		else cout<<f(b,c,d).a<<'\n';
	}
}