学姐的巧克力盒 - kito - 327217

记录编号	327217	评测结果	AAAAAAAAAA
题目名称	学姐的巧克力盒	最终得分	100
用户昵称	kito	是否通过	通过
代码语言	C++	运行时间	4.339 s
提交时间	2016-10-21 20:54:13	内存使用	61.33 MiB
显示代码纯文本
#include<cstdio>
#include<cmath>
using namespace std;
#define	fcl	fclose(stdin);	fclose(stdout);	return 0
	#define	SUBMIT 2333
typedef long long LL;
int n,m;
int K,p1,p2,phi;
int A[1000010];

char ch,CH[100];
int lll;
void Read(int& x){
	x=0;
	while(ch=getchar(),ch<'0'||ch>'9');
	x=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')	x=x*10+ch-'0';
}

void Qwrite(int a){
	lll=0;
	if(a==0){
		putchar('0');
		return;
	}
	while(a){
		CH[++lll]=(a%10)+'0';
		a/=10;
	}
	for(int i=lll;i>=1;--i){
		putchar(CH[i]);
	}
}

int Qpow(int a,int b,int p){
	int ans=1;
	while(b){
		if(b&1){
			ans=(ans*1ll*a)%p;
		}
		b>>=1;
		a=(a*1ll*a)%p;
	}
	return ans;
}

void GetPhi(){
	int x=(int)sqrt(double(p2)),p=p2;
	phi=1;
	for(int i=2;i<=x;++i){
		if(p%i==0){
			phi*=(i-1);
			p/=i;
			while(p%i==0){
				phi*=i;
				p/=i;
			}
		}
		if(p==1)	break;
	}
	if(p!=1)	phi*=(p-1);
}

/***************************work1*****************************/
int Tree1[4000010],Tree2[4000010];
int Qx,Qy;
int Ans;
#define mid ((l+r)>>1)
void Build(int rt,int l,int r){
	if(l==r){
		Read(A[l]);
		Tree1[rt]=A[l]%p1;
		Tree2[rt]=A[l]%phi;
		return;
	}
	Build(rt<<1,l,mid);
	Build(rt<<1|1,mid+1,r);
	Tree1[rt]=(Tree1[rt<<1]*1ll*Tree1[rt<<1|1])%p1;
	Tree2[rt]=(Tree2[rt<<1]*1ll*Tree2[rt<<1|1])%phi;
}

void Query1(int rt,int l,int r){
	if(Qx<=l&&Qy>=r){
		Ans=(Ans*1ll*Tree1[rt])%p1;
		return;
	}
	if(Qx<=mid)	Query1(rt<<1,l,mid);
	if(Qy>mid)	Query1(rt<<1|1,mid+1,r);
}

void Query2(int rt,int l,int r){
	if(Qx<=l&&Qy>=r){
		Ans=(Ans*1ll*Tree2[rt])%phi;
		return;
	}
	if(Qx<=mid)	Query2(rt<<1,l,mid);
	if(Qy>mid)	Query2(rt<<1|1,mid+1,r);
}

int Query1(int l,int r){
	Qx=l;	Qy=r;
	Ans=1;
	Query1(1,1,n);	return Ans;
}

int Query2(int l,int r){
	Qx=l;	Qy=r;	Ans=1;
	Query2(1,1,n);
	if(Ans==0)	Ans=phi;
	return Qpow(K,Ans,p2);
}

void work1(){
	Build(1,1,n);
	int a,l,r;
	for(int i=1;i<=m;++i){
		Read(a);	Read(l);	Read(r);
		if(a==1){
			if(p1==1){
				putchar('0');
				continue;
			}
			Qwrite(Query1(l,r));
		}
		else{
			if(p2==0){
				putchar('0');
				continue;
			}
			Qwrite(Query2(l,r));
		}
		puts("");
	}
}
/***************************work1*****************************/

/***************************work2*****************************/
int Mu[3][1000010],Inv[3][1000010],PP[3],BB[3],AA[3],X;
int Popow[1000010];
bool Target=false;
void ExGcd(int a,int b,int& x,int& y){
	if(b==0){
		x=1;	y=0;
		return;
	}
	ExGcd(b,a%b,x,y);
	int t=x;
	x=y;	y=t-(a/b)*y;
}

void query1(int l,int r){
	if(Target){
		X=(Mu[0][r]*1ll*Inv[0][l-1])%p1;
		Qwrite(X);
		//printf("%d\n",X);
		return;
	}
	X=0;
	for(int i=0;i<3;++i){
		AA[i]=(Mu[i][r]*1ll*Inv[i][l-1])%PP[i];
		X+=(AA[i]*1ll*BB[i])%p1;
		X%=p1;
	}
	//printf("%d\n",X);
	Qwrite(X);
}

void query2(int l,int r){
	X=0;
	for(int i=0;i<3;++i){
		AA[i]=(Mu[i][r]*1ll*Inv[i][l-1])%PP[i];
		X+=(AA[i]*1ll*BB[i])%p2;
		X%=p2;
	}
	if(X==0)	X+=p2;
	Qwrite(Popow[X]);
	//printf("%d\n",Popow[X]);
}

void work2(){
	if(p1){
		if(p1==1000000007)	Target=true;
		else{
			PP[0]=991;	PP[1]=997;	PP[2]=1009;
			BB[0]=PP[1]*PP[2];	BB[1]=PP[0]*PP[2];	BB[2]=PP[0]*PP[1];
		}
	}
	if(p2){
		if(p2==984359){
			PP[0]=2;	PP[1]=677;	PP[2]=727;
			BB[0]=PP[1]*PP[2];	BB[1]=PP[0]*PP[2];	BB[2]=PP[0]*PP[1];
		}
		else{
			PP[0]=2;	PP[1]=653;	PP[2]=757;
			BB[0]=PP[1]*PP[2];	BB[1]=PP[0]*PP[2];	BB[2]=PP[0]*PP[1];
		}
		Popow[0]=1;
		K%=p2;
		for(int i=1;i<=p2;++i){
			Popow[i]=(Popow[i-1]*1ll*K)%p2;
		}
		p2--;
	}
	if(!Target){
		int x,y;
		for(int i=0;i<3;++i){
			ExGcd(BB[i],PP[i],x,y);
			x%=PP[i];	x=(x+PP[i])%PP[i];
			if(p1)	BB[i]=(BB[i]*1ll*x)%p1;
			else	BB[i]=(BB[i]*1ll*x)%p2;
		}
	}
	Mu[0][0]=Mu[1][0]=Mu[2][0]=1;
	for(int i=1;i<=n;++i){
		Read(A[i]);
		if(Target){
			Mu[0][i]=(Mu[0][i-1]*1ll*A[i])%p1;
		}
		else{
			for(int j=0;j<3;++j){
				Mu[j][i]=(Mu[j][i-1]*1ll*A[i])%PP[j];
			}
		}
	}
	int y;
	if(Target){
		ExGcd(Mu[0][n],p1,Inv[0][n],y);
		Inv[0][n]%=p1;	Inv[0][n]=(Inv[0][n]+p1)%p1;
	}
	else{
		for(int j=0;j<3;++j){
			ExGcd(Mu[j][n],PP[j],Inv[j][n],y);
			Inv[j][n]%=PP[j];	Inv[j][n]=(Inv[j][n]+PP[j])%PP[j];
		}
	}
	for(int i=n-1;i>=0;--i){
		if(Target){
			Inv[0][i]=(Inv[0][i+1]*1ll*A[i+1])%p1;
		}
		else{
			for(int j=0;j<3;++j){
				Inv[j][i]=(Inv[j][i+1]*1ll*A[i+1])%PP[j];
			}
		}
	}
	int a,l,r;
	for(int i=1;i<=m;++i){
		Read(a);	Read(l);	Read(r);
		if(a==1){
			query1(l,r);
		}
		else{
			query2(l,r);
		}
		puts("");
	}
}

int main(){
	#ifdef SUBMIT
	freopen("chocolatebox.in","r",stdin);
	freopen("chocolatebox.out","w",stdout);
	#endif
	
	scanf("%d%d%d%d%d",&n,&m,&K,&p1,&p2);
	GetPhi();
	if(n<=500000){
		work1();
	}
	else{
		work2();
	}
	#ifndef SUBMIT
	getchar();	getchar();
	#endif
	fcl;
}