记录编号	342361	评测结果	AAAAAAAAAA
题目名称	学姐的巧克力盒	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	5.071 s
提交时间	2016-11-08 13:31:39	内存使用	171.95 MiB

#include<cstdio>
#include<cmath>
using namespace std;
const int N=1000010;
typedef long long ll;
int n,m,k,p1,p2,a[N],phi,ji[22][N],Ji[22][N];
inline int read(){
	int x=0;char ch=getchar();
	while (ch>'9'||ch<'0') ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
	return x;
}
inline void getphi(){
	int x=p2;phi=1;
	for (int i=2;i<=sqrt(x);i++)
	if (!(x%i)){
		int p=i-1;x/=i;
		while (!(x%i)) x/=i,p*=i;
		phi*=p;
	}
	if (x!=1) phi*=(x-1);
}
void build1(int l,int r,int h){
	if (l==r) return;
	int mid=(l+r)>>1;
	ji[h][mid]=a[mid]%p1;
	for (int i=mid-1;i>=l;i--) ji[h][i]=(ll)ji[h][i+1]*a[i]%p1;
	ji[h][mid+1]=a[mid+1]%p1;
	for (int i=mid+2;i<=r;i++) ji[h][i]=(ll)ji[h][i-1]*a[i]%p1;
	build1(l,mid,h+1);build1(mid+1,r,h+1);
}
void build2(int l,int r,int h){
	if (l==r) return;
	int mid=(l+r)>>1;
	Ji[h][mid]=a[mid]%phi;
	for (int i=mid-1;i>=l;i--) Ji[h][i]=(ll)Ji[h][i+1]*a[i]%phi;
	Ji[h][mid+1]=a[mid+1]%phi;
	for (int i=mid+2;i<=r;i++) Ji[h][i]=(ll)Ji[h][i-1]*a[i]%phi;
	build2(l,mid,h+1);build2(mid+1,r,h+1);
}
inline int ask1(int L,int R){
	if (L==R) return a[L]%p1;
	int l=1,r=n,h=0;
	while (1){
		int mid=(l+r)>>1;
		if (L<=mid&&R>mid) return (ll)ji[h][L]*ji[h][R]%p1;
		if (L>mid) l=mid+1;else r=mid;h++;
	}
}
inline int ask2(int L,int R){
	if (L==R) return a[L]%phi;
	int l=1,r=n,h=0;
	while (1){
		int mid=(l+r)>>1;
		if (L<=mid&&R>mid) return (ll)Ji[h][L]*Ji[h][R]%phi;
		if (L>mid) l=mid+1;else r=mid;h++;
	}
}
inline int mi(int x,int y){
	int ans=1;
	while (y){
		if (y&1) ans=(ll)ans*x%p2;
		x=(ll)x*x%p2;y>>=1;
	}
	return ans;
}
char s[20];
inline void print(int x){
	if (!x) {puts("0");return;}
	int l=0;for (;x;x/=10) s[l++]=x%10;
	while (l--) putchar(s[l]+'0');
	putchar('\n');
}
int main()
{
	freopen("chocolatebox.in","r",stdin);
	freopen("chocolatebox.out","w",stdout);
	n=read();m=read();k=read();p1=read();p2=read();
	getphi();
	for (int i=1;i<=n;i++) a[i]=read();
	if (p1) build1(1,n,0);
	if (p2) build2(1,n,0);
	while (m--){
		int ty=read(),l=read(),r=read();
		if (ty==2) print(mi(k,ask2(l,r)));
			else print(ask1(l,r));
	}
	return 0;
}