记录编号	326499	评测结果	AWAWATTTEE
题目名称	学姐的巧克力盒	最终得分	30
用户昵称	Mealy	是否通过	未通过
代码语言	C++	运行时间	8.928 s
提交时间	2016-10-21 08:31:37	内存使用	73.50 MiB

#include <iostream>
#include <cstdio>
#define u ree[tmpx]
#define lc ree[tmpx<<1]
#define rc ree[tmpx<<1^1]
using namespace std;

const int nmax=4000086;
typedef long long ll;

int n,q,k,FJ1,FJ2;
ll val[nmax];
ll ans,tmp;
int type,tmpl,tmpr;

//===============================================
class SegmengtTree
{
public:
	int l,r;
	ll pro;
}ree[nmax];


void SetTree(int tmpx,int tmpl,int tmpr)
{
	u.l=tmpl;
	u.r=tmpr;
	if(tmpl==tmpr)
	{
		u.pro=val[tmpl]%FJ1;
	}
	else
	{
		SetTree(tmpx<<1,tmpl,(tmpl+tmpr)>>1);
		SetTree(tmpx<<1^1,((tmpl+tmpr)>>1)+1,tmpr);
		u.pro=lc.pro*rc.pro%FJ1;
	}
}


ll QueryPro(int tmpx,int tmpl,int tmpr)
{
	if(tmpl<=u.l&&tmpr>=u.r)
	{
		return u.pro;
	}
	else
	{
		if(u.l!=u.r)
		{
			ll tmp=1;
			if(tmpl<=lc.r)
			{
				tmp=QueryPro(tmpx<<1,tmpl,tmpr)*tmp%FJ1;
			}
			if(tmpr>=rc.l)
			{
				tmp=QueryPro(tmpx<<1^1,tmpl,tmpr)*tmp%FJ1;
			}
			return tmp;
		}
	}
}
//===============================================


ll Phi(ll n)
{
    ll ret=1,i;
    for(i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            n/=i;
			ret*=i-1;
            while(n%i==0)
			{
				n/=i;
				ret*=i;
			}
        }
    }
    if(n>1)
	{
		ret*=n-1;
	}
    return ret;
}



ll QuickPow(ll base,ll exp)
{
	ll ans=1;
	exp%=Phi(FJ2);
	while(exp)
	{
		if(exp&1)
		{
			ans=(ans*base)%FJ2;
		}
		base=(base*base)%FJ2;
		exp>>=1;
	}
	return ans%FJ2;
}

//===============================================

void PreDo()
{
	scanf("%d%d%d%d%d",&n,&q,&k,&FJ1,&FJ2);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&val[i]);
	}
}
int main()
{
	freopen("chocolatebox.in","r",stdin);
	freopen("chocolatebox.out","w",stdout);
	PreDo();
	SetTree(1,1,n);
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d%d",&type,&tmpl,&tmpr);
		if(type==1)
		{
			ans=QueryPro(1,tmpl,tmpr);
			printf("%lld\n",ans%FJ1);
		}
		if(type==2)
		{
			tmp=QueryPro(1,tmpl,tmpr);
			ans=QuickPow(k,tmp);
			printf("%lld\n",ans);
		}
	}
	return 0;
}