BZOJ 4026: dC Loves Number Theory 可持久化线段树 + 欧拉函数 + 数学

逃离我推掉我的手 2021-11-16 05:28 161阅读 0赞

Code:

#include <bits/stdc++.h>
    #define ll long long  
    #define maxn 50207 
    #define setIO(s) freopen(s".in","r",stdin) 
    #define mod 1000777 
    using namespace std;
    struct Tree
    {
        int tot; 
        int lson[maxn*270],rson[maxn*270]; 
        ll mul[maxn*270];  
        int ins(int x,int l,int r,int p,ll v) 
        {
            int o=++tot; 
            lson[o]=lson[x],rson[o]=rson[x]; 
            if(x) mul[o]=mul[x]*v%mod; 
            else mul[o]=v; 
            if(l==r) return o; 
            int mid=(l+r)>>1;  
            if(p<=mid) lson[o]=ins(lson[x],l,mid,p,v); 
            else rson[o]=ins(rson[x],mid+1,r,p,v); 
            return o;
        } 
        ll query(int x,int l,int r,int L,int R) 
        {
            if(l>=L&&r<=R) return mul[x]; 
            ll re=1; 
            int mid=(l+r)>>1; 
            if(L<=mid) re=re*query(lson[x],l,mid,L,R)%mod; 
            if(R>mid) re=re*query(rson[x],mid+1,r,L,R)%mod; 
            return re;  
        }
    }tr; 
    int cnt,n,m; 
    int prime[1000004],vis[1000004],pre[1000006],rt[maxn],cur[maxn];  
    ll arr[maxn],mul[maxn]; 
    ll qpow(ll base,ll k) 
    {
        ll re=1; 
        while(k) 
        {
            if(k&1) re=re*base%mod; 
            base=base*base%mod; 
            k>>=1; 
        }
        return re; 
    }
    void Initialize(int N) 
    {
        for(int i=2;i<=N;++i) 
        {
            if(!vis[i]) prime[++cnt]=i; 
            for(int j=1;j<=cnt&&1ll*prime[j]*i<=N;++j) 
            {
                vis[i*prime[j]]=1; 
                if(i%prime[j]==0) break; 
            }
        } 
        for(int i=1;i<=n;++i) 
        {
            int x=arr[i],cc=0;   
            rt[i]=rt[i-1];  
            if(x==1) 
            {
                rt[i]=tr.ins(rt[i-1],1,n,i,1); 
                continue; 
            }
            cur[++cc]=rt[i];   
            for(int j=1;j<=cnt&&1ll*prime[j]*prime[j]<=x;++j) 
            {
                if(x%prime[j]==0) 
                { 
                    if(pre[prime[j]])
                    {
                        cur[cc+1]=tr.ins(cur[cc],1,n,pre[prime[j]],1ll*prime[j]*qpow((prime[j]-1), mod-2)%mod); 
                        ++cc; 
                    }
                    cur[cc+1]=tr.ins(cur[cc],1,n,pre[prime[j]]=i,1ll*(prime[j]-1)*qpow(prime[j],mod-2)%mod); 
                    ++cc;     
                    while(x%prime[j]==0) x/=prime[j];       
                }
            }
            if(x>1) 
            {
                if(pre[x]) 
                { 
                    cur[cc+1]=tr.ins(cur[cc],1,n,pre[x],1ll*x*qpow((x-1), mod-2)%mod); 
                    ++cc; 
                }
                cur[cc+1]=tr.ins(cur[cc],1,n,pre[x]=i,1ll*(x-1)*qpow(x,mod-2)%mod); 
                ++cc;     
            }
            rt[i]=cur[cc];  
            for(int i=1;i<=cc;++i) cur[i]=0; 
        }
    } 
    int main() 
    {
        // setIO("input"); 
        scanf("%d%d",&n,&m); 
        int mx=0; 
        mul[0]=1;  
        for(int i=1;i<=n;++i) 
        {
            scanf("%lld",&arr[i]); 
            mul[i]=mul[i-1]*arr[i]%mod; 
            mx=max(mx, (int)arr[i]); 
        } 
        Initialize(mx);   
        ll lastans=0; 
        for(int i=1;i<=m;++i) 
        {
            // lastans=0;
            int l,r; 
            scanf("%d%d",&l,&r); 
            l^=lastans,r^=lastans;             
            ll rev=qpow(mul[l-1],mod-2); 
            lastans=mul[r]*rev%mod*tr.query(rt[r],1,n,l,r)%mod;    
            printf("%lld\n",lastans); 
        }
        return 0;
    }

转载于:https://www.cnblogs.com/guangheli/p/11247750.html