记录编号	594855	评测结果	AAAAAAAAAA
题目名称	学姐的巧克力盒	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	7.589 s
提交时间	2024-10-05 20:25:25	内存使用	16.40 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fi first
#define in inline
#define se second
#define mp make_pair
#define pb push_back
const int N = 1e6+10;

ll read(){
	ll x = 0,f = 1;char c = getchar();
	for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
	for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
	return x * f;
}


int n,m;
ll k,p1,p2,p3;
ll a[N];

struct segment{
	ll s[N<<2],mod;
	void pushup(int p){s[p] = s[p<<1] * s[p<<1|1] % mod;}
	void build(int p,int l,int r){
		if(l == r)return s[p] = a[l],void();
		int mid = l + r >> 1;
		build(p<<1,l,mid),build(p<<1|1,mid+1,r);
		pushup(p);
	}
	ll ask(int p,int l,int r,int L,int R){
		if(L > r || R < l)return 1;
		if(L <= l && r <= R)return s[p];
		int mid = l + r >> 1;
		return ask(p<<1,l,mid,L,R) * ask(p<<1|1,mid+1,r,L,R) % mod;
	}
}s1,s2;


ll ksm(ll x,ll y,ll mod){
	ll ans = 1;
	while(y){
		if(y & 1)ans = ans * x % mod;
		x = x * x % mod,y >>= 1;
	}return ans;
}
ll phi(ll n){
	ll ans = n;
	for(int i = 2;i <= sqrt(n);i++){
		if(n % i == 0){
			ans = ans / i * (i-1);
			while(n % i == 0)n /= i;
		}
	}
	if(n > 1)ans = ans / n * (n - 1);
	return ans;
}

int main(){
	freopen("chocolatebox.in","r",stdin);
	freopen("chocolatebox.out","w",stdout);
	n = read(),m = read(),k = read(),p1 = read(),p2 = read();
	p3 = phi(p2);
	for(int i = 1;i <= n;i++)a[i] = read();
	s1.mod = p1;
	if(p1)s1.build(1,1,n);
	s2.mod = p3;
	if(p3)s2.build(1,1,n);
	for(int i = 1;i <= m;i++){
		int op = read(),l = read(),r = read();
		if(op == 1)printf("%lld\n",s1.ask(1,1,n,l,r));
		else printf("%lld\n",ksm(k,s2.ask(1,1,n,l,r) + p3,p2));
	}

	return cerr<<clock()<<"ms"<<endl,0;

}