比赛 |
2024暑假C班集训E |
评测结果 |
AAAAAAAAWAWAAAAATATA |
题目名称 |
相逢是问候 |
最终得分 |
80 |
用户昵称 |
┭┮﹏┭┮ |
运行时间 |
9.265 s |
代码语言 |
C++ |
内存使用 |
9.95 MiB |
提交时间 |
2024-07-14 11:48:48 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e4+10,M = N<<2;
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,mx;
ll mod,c,a[N],s[N];
int p[1000010],phi[1000010],cnt;
bool v[1000010];
void prework(){
phi[1] = 1;
for(int i = 2;i <= 1e6;i++){
if(!v[i])p[++cnt] = i,phi[i] = i-1;
for(int j = 1;p[j] <= 1e6 / i;j++){
v[i * p[j]] = 1;
if(i % p[j] == 0){phi[i * p[j]] = phi[i] * p[j];break;}
else phi[i * p[j]] = phi[i] * phi[p[j]];
}
}
// for(int i = 1;i <= 20;i++)cout<<phi[i]<<' ';
// cout<<endl;
}
ll get(ll x){
if(x <= 1e6)return phi[x];
ll ans = x;
for(int i = 2;i <= sqrt(x);i++){
if(x % i == 0){
ans = ans / i * (i-1ll);
while(x % i == 0)x /= i;
}
}
if(x > 1)ans = ans / x * (x-1);
return ans;
}
ll ksm(ll x,ll y,ll mod,bool &flag){
ll ans = 1;
while(y){
if(y & 1){
if(ans * x >= mod)flag = 1;
ans = ans * x % mod;
}
if(x * x >= mod)flag = 1;
x = x * x % mod,y >>= 1;
}return ans;
}
struct segment{
ll sum[M],la[M];
void pushup(int p){sum[p] = (sum[p<<1] + sum[p<<1|1]) % mod,la[p] = min(la[p<<1],la[p<<1|1]);}
void build(int p,int l,int r){
if(l == r)return sum[p] = a[l] %= mod,void();
int mid = l + r >> 1;
build(p<<1,l,mid),build(p<<1|1,mid+1,r);
pushup(p);
}
ll find(ll x,int num){
ll zhi = x;
if(zhi >= s[num])zhi = x % s[num] + s[num];
for(;num > 0;num--){
bool flag = 0;
zhi = ksm(c,zhi,s[num-1],flag);
if(flag)zhi += s[num-1];
}
return zhi % mod;
}
void modify(int p,int l,int r,int L,int R){
if(la[p] >= mx)return;
if(l == r)return sum[p] = find(a[l],++la[p]),void();
int mid = l + r >> 1;
if(L <= mid)modify(p<<1,l,mid,L,R);
if(R > mid)modify(p<<1|1,mid+1,r,L,R);
pushup(p);
}
ll ask(int p,int l,int r,int L,int R){
if(L <= l && r <= R)return sum[p];
int mid = l + r >> 1;
if(R <= mid)return ask(p<<1,l,mid,L,R);
else if(L > mid)return ask(p<<1|1,mid+1,r,L,R);
else return (ask(p<<1,l,mid,L,R) + ask(p<<1|1,mid+1,r,L,R)) % mod;
}
}t;
void find(ll x){
s[++mx] = x;
if(x == 1)return;
find(get(x));
}
int main(){
freopen("verbinden.in","r",stdin);
freopen("verbinden.out","w",stdout);
n = read(),m = read(),mod = read(),c = read();
prework();
for(int i = 1;i <= n;i++)a[i] = read();
mx = -1;
find(mod);
t.build(1,1,n);
for(int i = 1;i <= m;i++){
int op = read(),l = read(),r = read();
if(!op)t.modify(1,1,n,l,r);
else printf("%lld\n",t.ask(1,1,n,l,r));
}
return 0;
}