70分求助

回复帖子

@_Veritas  2021-02-23 21:32 回复

提交记录

#include<iostream>
#include<cstdio>
#define int long long
#define MAXN 500005
using namespace std;
int a[MAXN],c[MAXN],n,m;
struct Ans{int a;bool b;};

inline int read(){
    int x=0;char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}

inline int lowbit(int x){return x&(-x);}
inline void update(int i,int k){
    while(i<=n){
        c[i]+=k;
        i+=lowbit(i);
    }
}
inline int query(int i){
    int sum=0;
    while(i>0){
        sum+=c[i];
        i-=lowbit(i);
    }
    return sum;
}

const int MAXP=100000008;
int prime[MAXP],cnt,phi[MAXP];bool notprime[MAXP];
void Euler(int n){
    phi[1]=1;
    for(int i=2;i<=n;++i){
        if(!notprime[i]) prime[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt&&i*prime[j]<=n;++j){
            notprime[i*prime[j]]=true;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
    return;
}
int gcd(int a,int b){while(b^=a^=b^=a%=b);return a;}

Ans pow(int a,int b,int p){
    Ans ans;ans.a=1;ans.b=true;int base=a,i;
    for(i=1;i<=b;i<<=1){
        if(b&i)
            if((ans.a=ans.a*base)>=p)
                {ans.b=false;break;}
        if((base=base*base)>=p) break;
    }
    for(;i<=b;i<<=1)
        if(b&i)
            {ans.b=false;break;}
    ans.a=1;base=a%p;
    for(int i=1;i<=b;i<<=1){
        if(b&i)
            ans.a=ans.a*base%p;
        base=base*base%p;
    }
    return ans;
}
Ans f(int l,int r,int p){
    a[l]=query(l);
    Ans ans,x;
    if(p==1){ans.a=0;ans.b=false;return ans;}
    if(l==r){ans.a=a[l]%p;ans.b=(a[l]<p);return ans;}
    x=f(l+1,r,phi[p]);
    if(gcd(a[l],p)==1) return pow(a[l],x.a,p);
    if(x.b) return pow(a[l],x.a,p);
    return pow(a[l],x.a+phi[p],p);
}

signed main(){
    n=read();m=read();
    Euler(20000001);
    for(int i=1;i<=n;++i) a[i]=read();
    for(int i=n;i>=1;--i) a[i]=a[i]-a[i-1];
    for(int i=1;i<=n;++i) update(i,a[i]);
    for(int i=1,a,b,c,d;i<=m;++i){
        a=read();b=read();c=read();d=read();
        if(a==1) {update(b,d);update(c+1,-d);}
        else cout<<f(b,c,d).a<<'\n';
    }
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。