记录编号	613069	评测结果	AAAAAAAAAA
题目名称	数据结构题	最终得分	100
用户昵称	rzzakioi	是否通过	通过
代码语言	C++	运行时间	11.059 s
提交时间	2026-02-28 13:01:21	内存使用	189.10 MiB

#include<cstdio>
#define int long long
using namespace std;
int n,m,a[500005],prime[2000005],phi[20000005],cnt;
bool vis[20000005];
int tr[500005];
struct node{
    int val;
    bool flag;
};
int lowbit(int x){
    return x&(-x);
}
void add(int x,int v){
    for(int i=x;i<=n;i+=lowbit(i)){
        tr[i]+=v;
    }
}
int query(int x){
    int ans=0;
    for(int i=x;i>=1;i-=lowbit(i)){
        ans+=tr[i];
    }
    return ans;
}
int fpow(int x,int y,int mod){
    int ans=1;
    while(y){
        if(y&1){
            ans*=x;
            ans%=mod;
        }
        x*=x;
        x%=mod;
        y>>=1;
    }
    return ans;
}
node f(int l,int r,int mod){
    int num=query(l);
    if(mod==1)return {0,num>=mod};
    if(num==1)return {1%mod,1>=mod};
    if(l==r)return {num%mod,num>=mod};
    node mi=f(l+1,r,phi[mod]);
    if(mi.flag)mi.val+=phi[mod];
    bool b=0;
    if(num>=2){
        int qwq=1;
        for(int i=1;i<=mi.val;i++){
            qwq*=num;
            if(qwq>=mod){
                b=1;
                break;
            }
        }
    }
    return {fpow(num%mod,mi.val,mod),b};
}
signed main(){
    phi[1]=1;
    for(int i=2;i<=20000000;i++){
        if(!vis[i]){
            prime[++cnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=cnt&&i*prime[j]<=20000000;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0){
                phi[i*prime[j]]=prime[j]*phi[i];
                break;
            }
            phi[i*prime[j]]=(prime[j]-1)*phi[i];
        }
    }
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        add(i,a[i]-a[i-1]);
    }
    for(int i=1;i<=m;i++){
        int op,l,r,x;
        scanf("%lld%lld%lld%lld",&op,&l,&r,&x);
        if(op==1){
            add(l,x);
            add(r+1,-x);
        }
        else{
            printf("%lld\n",f(l,r,x).val);
        }
    }
    return 0;
}