求助P3747

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+2;
int n,m,p,c,a[N<<2],sum[N<<2],phi;

int get_phi(int n)
{
	int ans=n;
	for(int i=2;i<=sqrt(n);i++)
	{
		if(n%i==0)
		{
			ans=ans/i*(i-1);
			while(n%i==0) n/=i;
		}
	}
	if(n>1) ans=ans/n*(n-1);
	return ans;
}

int quickpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1) res=res*a%p;
		a=a*a%p;
		b>>=1;
	}
	return res;
}

void update(int x)
{
	sum[x]=(sum[x<<1]+sum[x<<1|1])%p;
}

void build(int l,int r,int x)
{
	if(l==r)
	{
		sum[x]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,x<<1);
	build(mid+1,r,x<<1|1);
	update(x);
}

int query(int a,int b,int l,int r,int x)
{
	if(a<=l&&b>=r)
	{
		return sum[x];
	}
	int mid=(l+r)>>1,ans=0;
	if(a<=mid) ans=(ans+query(a,b,l,mid,x<<1))%p;
	if(b>mid) ans=(ans+query(a,b,mid+1,r,x<<1|1))%p;
	return ans;
}

void change(int a,int b,int l,int r,int x)
{
	if(l==r&&a<=l&&b>=r)
	{
		if(sum[x]<phi) sum[x]=quickpow(c,sum[x]);
		else sum[x]=quickpow(c,sum[x]%phi+phi);
		return;
	}
	int mid=(l+r)>>1;
	if(a<=mid) change(a,b,l,mid,x<<1);
	if(b>mid) change(a,b,mid+1,r,x<<1|1);
	update(x);
}

signed main()
{
	scanf("%lld%lld%lld%lld",&n,&m,&p,&c);
	phi=get_phi(p);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
	}
	build(1,n,1);
	while(m--)
	{
		int op,l,r;
		scanf("%lld%lld%lld",&op,&l,&r);
		if(op==0)
		{
			change(l,r,1,n,1);
		}
		if(op==1)
		{
			printf("%lld\n",query(l,r,1,n,1));
		}
	}
	return 0;
}