记录编号	326401	评测结果	AAAATTTTEE
题目名称	学姐的巧克力盒	最终得分	40
用户昵称	Hzoi_Yniverse	是否通过	未通过
代码语言	C++	运行时间	9.287 s
提交时间	2016-10-21 07:44:37	内存使用	68.98 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
const long long maxn=1000010;
long long n,m,k,p1,p2,mm,phi;
long long a[maxn],c[maxn*4],c2[maxn*4];
void Build(long long rt,long long l,long long r){
	if(l==r){ 
		c[rt]=a[l]%p1; 
		if(phi)c2[rt]=a[l]%phi; 
    return; }
	long long mid=(l+r)>>1;
	Build(lson); Build(rson);
	c[rt]=(c[rt<<1]*c[rt<<1|1])%p1;
	if(phi)c2[rt]=(c2[rt<<1]*c2[rt<<1|1])%phi;
}
long long Qery(long long s,long long t,long long rt,long long l,long long r){
     //if(s==446)printf("%lld %lld\n",l,r);
	if(s<=l&&t>=r) return c[rt];
	long long mid=(l+r)>>1;
	if(t<=mid) return Qery(s,t,lson);
	if(s>mid) return Qery(s,t,rson);
	return (Qery(s,t,lson)*Qery(s,t,rson))%p1;
}
long long Qery2(long long s,long long t,long long rt,long long l,long long r){
	if(s<=l&&t>=r) return c2[rt];
	long long mid=(l+r)>>1;
	if(t<=mid) return Qery2(s,t,lson);
	if(s>mid) return Qery2(s,t,rson);
	return (Qery2(s,t,lson)*Qery2(s,t,rson))%phi;
}
long long Getphi(long long x){
	long long ans=x;
	for(int i=2;i*i<=x;i++){
		if(x%i==0){
			while(x%i==0) x/=i;
			ans=ans/i*(i-1);
		}
	}
	if(x>1) ans=ans/x*(x-1);
	return ans;
}
long long quickpow(long long x,long long m){
	long long ans=1;
	while(m){
		if(m&1) ans*=x;
		x*=x; m>>=1;
		ans%=p2; x%=p2;
	}
	return ans%p2;
}
int main(){
	freopen("chocolatebox.in","r",stdin);
	freopen("chocolatebox.out","w",stdout);
	scanf("%lld%lld%lld%lld%lld",&n,&m,&k,&p1,&p2);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	phi=Getphi(p2);//printf("phi==%d\n",phi);
    Build(1,1,n);
	for(int i=1;i<=m;i++){
		long long z,x,y;scanf("%lld%lld%lld",&z,&x,&y);
		if(z==1) printf("%lld\n",Qery(x,y,1,1,n)%p1);
		else{
			mm=Qery2(x,y,1,1,n)%phi+phi;
			printf("%lld\n",quickpow(k,mm));
		}
	}
	//system("pause"); 
	return 0;
}