记录编号	326352	评测结果	AAAAAAAAAA
题目名称	学姐的巧克力盒	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	7.759 s
提交时间	2016-10-21 07:30:02	内存使用	33.86 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn=1100010;//1048576
LL euler_phi(LL);
LL qmul(int,int,const LL*,LL);
LL qpow(LL,LL,LL);
int n,m,M=1,l,r,d;
LL k,a[maxn<<1],b[maxn<<1],p1,p2,phi;
int main(){
#define MINE
#ifdef MINE
	freopen("chocolatebox.in","r",stdin);
	freopen("chocolatebox.out","w",stdout);
#endif
	scanf("%d%d%lld%lld%lld",&n,&m,&k,&p1,&p2);
	if(!p1)p1=1ll;
	if(!p2)p2=1ll;
	while(M<n+2)M<<=1;
	phi=euler_phi(p2);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i+M]);
		b[i+M]=a[i+M]%phi;
		a[i+M]%=p1;
	}
	for(int i=n+M+1;i<(M<<1);i++)a[i]=b[i]=1ll;
	a[M]=b[M]=1ll;
	for(int i=M-1;i;i--){
		a[i]=a[i<<1]*a[i<<1|1]%p1;
		b[i]=b[i<<1]*b[i<<1|1]%phi;
	}
	while(m--){
		scanf("%d%d%d",&d,&l,&r);
		if(d==1)printf("%lld\n",qmul(l,r,a,p1));
		else printf("%lld\n",qpow(k,qmul(l,r,b,phi),p2));
	}
	//printf("\n");for(int i=1;i<(M<<1);i++)printf("%lld ",a[i]);
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#endif
	return 0;
}
LL euler_phi(LL n){
	LL ans=n;
	int m=(int)(sqrt(n)+0.5);
	for(int i=2;i<=m;i++)if(n%i==0){
		ans=ans/i*(i-1);
		do n/=i;while(n%i==0);
	}
	if(n>1)ans=ans/n*(n-1);
	return ans;
}
LL qmul(int l,int r,const LL *a,LL p){
	LL ans=1ll;
	for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1){
		if(~l&1)ans=ans*a[l^1]%p;
		if(r&1)ans=ans*a[r^1]%p;
	}
	return ans;
}
LL qpow(LL a,LL b,LL p){
	LL ans=1ll;
	for(;b;b>>=1,a=a*a%p)if(b&1ll)ans=ans*a%p;
	return ans%p;
}