P12524 题解

hyman00 · 2025-05-21 15:47:23 · 题解

出题人对离散对数有什么执念吗，连续两个题都要用。

平方最后算，先拆贡献，容易发现

因此统计所有素数幂在多少个子序列出现了即可。

考虑莫队，如何插入一个数，枚举他的所有素数幂的因子，假设它已经在区间内出现了 k 次，则贡献是答案乘上 p^{2^{\max(k-1,0)}}，其中 2^{\max(k-1,0)} 是 k 个数中长度偶数的子序列个数。可以做到 O(n^{1.5}\log^2n)。

尝试去掉一个 log，上面的 2 的幂可以预处理，下面的可以用离散对数转成乘法计算，做到 O(n^{1.5}\log n)。

代码粘了一堆板子。

const int P=MOD,g=3;
namespace Math{
    unordered_map<int,int>pm(5000000);
    int ff[32000];
    vi pr;
    int b,c,n,tc;
    il int qp(int x,int y){
        int z=1;
        for(;y;(x*=x)%=P,y>>=1)if(y&1)(z*=x)%=P;
        re z;
    }
    il int _Log(int x){
        x=qp(x,P-2);
        for(int i=b;;i+=b){
            (x*=c)%=P;
            if(pm.count(x))re i-pm[x];
        }
    }
    void init(){
        b=500000;c=1;
        rept(i,1,b+1){
            (c*=g)%=P;
            pm[c]=i;
        }
        n=min((int)sqrt(P)+2,P);
        rept(i,2,n){
            if(!ff[i]){
                ff[i]=_Log(i);
                pr.pb(i);
            }
            for(int j:pr){
                if(i*j>=n)break;
                ff[i*j]=(ff[i]+ff[j])%(P-1);
                if(i%j==0)break;
            }
        }
        tc=_Log(P-1);
    }
    il int Log(int x){
        if(x<n)re ff[x];
        int y=P/x,z=P%x;
        if(z*2<=x)re (tc+Log(z)-ff[y]+P-1)%(P-1);
        re (Log(x-z)-ff[y+1]+P-1)%(P-1);
    }
}
const int N=100005,B=330;
int n,q;
int a[N],c[N],pw[N],ans[N],cx[N],icx[N];
vector<array<int,4>>qy;
vi tp[N],pr;
int isp[N];
il int qp(int x,int y){
    int z=1;
    for(;y;(x*=x)%=MOD,y>>=1)if(y&1)(z*=x)%=MOD;
    re z;
}
int tmp;
il void ins(int x){
    for(int i:tp[x]){
        (tmp+=cx[i]*pw[c[i]])%=(MOD-1);
        c[i]++;
    }
}
il void era(int x){
    for(int i:tp[x]){
        c[i]--;
        (tmp-=cx[i]*pw[c[i]])%=(MOD-1);
    }
}
void run(){
    Math::init();
    rept(i,2,N){
        if(!isp[i]){
            pr.pb(i);
            int ri=Math::Log(i);
            for(int j=i;j<N;j*=i){
                cx[j]=ri;
                for(int k=j;k<N;k+=j)tp[k].pb(j);
            }
        }
        for(int j:pr){
            if(i*j>=N)break;
            isp[i*j]=1;
            if(i%j==0)break;
        }
    }
    pw[0]=pw[1]=1;
    rept(i,2,N)pw[i]=pw[i-1]*2%(MOD-1);
    cin>>n>>q;
    rep(i,n)cin>>a[i];
    rep(i,q){
        int l,r;
        cin>>l>>r;
        l--;
        qy.pb({l/B,r,l,i});
    }
    sort(all(qy));
    tmp=1;
    int l=0,r=0;
    for(auto it:qy){
        while(l>it[2])ins(a[--l]);
        while(r<it[1])ins(a[r++]);
        while(l<it[2])era(a[l++]);
        while(r>it[1])era(a[--r]);
        ans[it[3]]=tmp;
    }
    rep(i,q)cout<<qp(g,MOD*2-4+ans[i]*2)<<"\n";
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T=1;
//  cin>>T;
    while(T--)
        run();
    re 0;
}