11 18

shiruoyu114514 · 2025-11-18 20:16:44 · 题解

定义一个序列 \{a_n\} 合法，当且仅当对于任意一个质数 p，\{\gcd(a_n,p^{+\infty}\}\} （非严格）单峰。

一个序列的权值 f(a) 为，将这个序列的 1 改成任意值（包括 1）使得序列合法，并且 \operatorname{lcm} 不增的方案数。

每次询问给定 [L,R]，求 \sum \limits_{[l,r] \in [L,R]} f(a[l:r])。

显然每个质因数独立。

结论：对于两个相邻的 i,j 使得 a_i \neq 1,a_j \neq 1 而言，对于任何一个 p，记录 v_i 为 a_i 在 p 上的指数，如果 v_i \ge v_j，则对于任意 i<k<j，v_k \in [v_j,v_i]，且序列递减。

证明：显然 v_k \ge v_j，否则 i,k,j 为一个谷。v_k \le v_i，否则 v_k>v_i,v_k>v_j，要么存在一个 t 使得 t<i 且 v_t>v_i，此时 t,i,k 构成一个谷；要么存在一个 t 使得 t>j 且 v_t>v_j，此时 k,j,t 构成一个谷；否则没有一个原有的 t 使得 v_t \le v_j < v_k，k 为全局最大值，此时违反 \operatorname{lcm} 规则。

于是每一段的选择就独立了，就可以比较方便地进行统计了。具体地，对于一个 p 而言，假如一个长度为 l 的 1 连续段左右两侧的 v 值分别为 a,b，那么相当于是 l+1 个变量，和值为 |a-b| 的方案数。方案数为 \binom{|a-b|+l}{l}。特别地，如果左右两边没有值的话 v 视为 0。

具体地，我们考虑进行扫描线，然后维护 [i,r] 序列的权值，之后进行历史和。当 r 扫描到一个 1 的时候，设 i 为最大的数使得 (i,r] 全是 1，则只对 [1,i] 进行前缀积即可。否则，我们暴力更新所有 j \in (i,r) 的 [j,r] 权值，然后对 [1,i] 进行前缀积。最后，设 v 为最大的数使得 (v,r] 本身权值不为 0（即只保留非 1 位置后合法），对 [1,v) 区间乘以 0。

最后再说一下怎么求最大的 v 使得 (v,r] 合法。

BC 性质：我们在往右扫描 r 的时候额外维护一个 p，满足 [p,r] 不降。当 v_{r+1}>v_r 时，ans \leftarrow p，否则 p \leftarrow r+1。

B 性质：对于每一个质因子都跑一遍显然是不现实的。不过观察到对于 BC 版本而言，如果序列的末尾的 v 值为 0，那么再插一个 0 不会改变任何东西。所以在扫描 r 时只需要对 r 与 r-1 的质因子的并更新即可。

无特殊性质：我们改为维护最大的 v 使得 a_v \neq 1 且 [v,r] 合法。令 lst_i 为 i 左边最大的 p 使得 a_p \neq 1，则真正的答案为 lst_{v-1}。特判前缀 1。

设矩阵大小 K=2，则时间复杂度 O(K^3n \log n)。（使用矩阵维护历史和）

#include<bits/stdc++.h>

using namespace std;

#define int long long

constexpr int mod=1e9+7;
constexpr int maxn=5e5;

void veradd(int& x,int y){
    x+=y;
    if(x>=mod){
        x-=mod;
    }
}

int add(int x,int y){
    return x+y-(x+y>=mod)*mod;
}

namespace number{

constexpr int maxn=5e5;
int notprime[maxn+5];
int minprime[maxn+5];
vector<int> primes;

void init(){
    notprime[1]=1;
    minprime[1]=1;
    for(int i=2;i<=maxn;i++){
        if(!notprime[i]){
            primes.push_back(i);
            minprime[i]=i;
        }
        for(auto j:primes){
            if(i*j>maxn){
                break;
            }
            notprime[i*j]=1;
            minprime[i*j]=j;
            if(i%j==0){
                break;
            }
        }
    }
}

unordered_map<int,int> split(int x){
    unordered_map<int,int> ans;
    while(x!=1){
        int p=minprime[x];
        int cnt=0;
        while(p==minprime[x]){
            x/=p;
            cnt++;
        }
        ans[p]=cnt;
    }
    return ans;
}

}

namespace historysum{
    struct info{
        int a[2];

        info(){
            a[0]=a[1]=0;
        }

        int& operator [](int x){
            return a[x];
        }
    };

    struct Matrix{
        int a[2][2];

        Matrix(){
            a[0][0]=a[1][1]=1;
            a[1][0]=a[0][1]=0;  
        }

        int* operator [](int x){
            return a[x];
        }
    };

    Matrix Time(int x){
        Matrix ret;
        ret.a[0][0]=x;
        return ret;
    }

    Matrix Sum(){   
        Matrix ret;
        ret.a[0][1]=1;
        return ret;
    }

    void operator *= (info& a,Matrix t){
        info ret;
        ret[0]=add(a[0]*t[0][0]%mod,a[1]*t[1][0]%mod);
        ret[1]=add(a[0]*t[0][1]%mod,a[1]*t[1][1]%mod);
        a=ret;
    }

    void operator += (info& a,info b){
        veradd(a[0],b[0]);
        veradd(a[1],b[1]);
    }

    info operator + (info a,info b){
        info ret;
        ret[0]=add(a[0],b[0]);
        ret[1]=add(a[1],b[1]);
        return ret;
    }

    Matrix operator * (Matrix a,Matrix b){
        Matrix ret;
        ret[0][0]=(a[0][0]*b[0][0]+a[0][1]*b[1][0])%mod;
        ret[0][1]=(a[0][0]*b[0][1]+a[0][1]*b[1][1])%mod;
        ret[1][0]=(a[1][0]*b[0][0]+a[1][1]*b[1][0])%mod;
        ret[1][1]=(a[1][0]*b[0][1]+a[1][1]*b[1][1])%mod;
        return ret;
    }

    info sum[(maxn<<2)+5];
    Matrix tag[(maxn<<2)+5];
    bool havetag[(maxn<<2)+5];

    void build(int now,int from,int to){
        sum[now][0]=to-from+1;
        if(from==to)
            return;
        int mid=(from+to)>>1;
        build(now<<1,from,mid);
        build(now<<1|1,mid+1,to);
    }

    void on(int now,Matrix tg){
//      cerr<<"Onbeg!: "<<now<<"\n";
        sum[now]*=tg;
    //  cerr<<"Onmid!\n";
        if(havetag[now]==0){
            tag[now]=tg;
    //  cerr<<"Oned!:\n";
            havetag[now]=1;
        }
        else{
            tag[now]=tag[now]*tg;
        }
    }

    void pushup(int now){
        sum[now]=sum[now<<1]+sum[now<<1|1];
    }

    void pushdown(int now){
        if(havetag[now]){
            on(now<<1,tag[now]);
            on(now<<1|1,tag[now]);
            tag[now]=Matrix();
            havetag[now]=0;
        }
    }

    void update(int now,int from,int to,int ql,int qr,Matrix v){
//      if(now==1){
//          if(v[0][1]==0){
//              cout<<"Update "<<ql<<" "<<qr<<" "<<v[0][0]<<"\n";
//          }
//      }
//      cerr<<from<<" "<<to<<" "<<ql<<" "<<qr<<"\n";
        if(from==ql&&to==qr){
            on(now,v);
            return;
        }
        pushdown(now);
//      cerr<<"Pushdown!\n";
    //  exit(0);
        int mid=(from+to)>>1;
        if(ql<=mid){
            update(now<<1,from,mid,ql,min(qr,mid),v);
        }
        if(mid<qr){
            update(now<<1|1,mid+1,to,max(mid+1,ql),qr,v);
        }
        pushup(now);
    }   

    info quary(int now,int from,int to,int ql,int qr){
        if(from==ql&&to==qr){
            return sum[now];
        }
        pushdown(now);
        int mid=(from+to)>>1;
        info ans;
        if(ql<=mid){
            //veradd(ans,quary(now<<1,from,mid,ql,min(mid,qr)));
            ans+=quary(now<<1,from,mid,ql,min(mid,qr));
        }
        if(mid<qr){
            ans+=quary(now<<1|1,mid+1,to,max(mid+1,ql),qr);
        }
        return ans;
    }
}

namespace Binom{
    constexpr int Bmax=maxn+50;

    int frac[Bmax+5];
    int ifrac[Bmax+5];

    int ksm(int a,int b){
        int ans=1;
        while(b){
            if(b&1){
                ans=ans*a%mod;
            }
            a=a*a%mod;
            b>>=1;
        }
        return ans;
    }

    void init(){
        frac[0]=1;
        for(int i=1;i<=Bmax;i++){
            frac[i]=frac[i-1]*i%mod;
        }
        ifrac[Bmax]=ksm(frac[Bmax],mod-2);
        for(int i=Bmax-1;i>=0;i--){
            ifrac[i]=ifrac[i+1]*(i+1)%mod;
        }
    }

    int binom(int n,int m){
        return frac[n]*ifrac[n-m]%mod*ifrac[m]%mod;
    }
}

using Binom::binom;
using historysum::update;
using historysum::Time;
using historysum::Sum;
using historysum::update;
using number::split;
using historysum::quary;
using Binom::ksm;

int n,q;
int a[maxn+5];
int lft[maxn+5];
int answer[maxn+5];
unordered_map<int,int> splited[maxn+5];
vector<pair<int,int>> quarys[maxn+5];

int lownotdown[maxn+5];
int llim[maxn+5];
int Mx=1;

void calc(int v,int pos,int lastpos){
    int lastv=splited[lastpos].count(v)?splited[lastpos][v]:0;
    int nowv=splited[pos].count(v)?splited[pos][v]:0;
    if(nowv>lastv){
        //  cout<<pos<<":"<<v<<" Update! "<<nowv<<" "<<lastv<<"\n";
        Mx=max(Mx,lownotdown[v]);
    }
    else if(nowv<lastv){
        lownotdown[v]=pos;
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    Binom::init();
    number::init();
    cin>>n>>q;
    historysum::build(1,1,n);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]==1){
            lft[i]=lft[i-1];
        }
        else{
            lft[i]=i;
        }
    }
    for(int i=1;i<=n;i++){
        splited[i]=split(a[i]);
    }
    for(int i=1;i<=q;i++){
        int l,r;
        cin>>l>>r;
        quarys[r].push_back(make_pair(l,i));
    }
    llim[0]=1;
    for(int i=1;i<=n;i++){
        if(a[i]==1){
            llim[i]=llim[i-1];
        }
        else{
            int lpos=lft[i-1];
            if(lpos==0){
                for(int j=1;j<=maxn;j++){
                    lownotdown[j]=i;
                }
                Mx=i;
            }
            else{
                for(auto j:splited[lpos]){
                    calc(j.first,i,lpos);
                }
                for(auto j:splited[i]){
                    if(!splited[lpos].count(j.first)){
                        calc(j.first,i,lpos);
                    }
                }
            }
            llim[i]=lft[Mx-1]+1;
        }
    }
    for(int i=1;i<=n;i++){
    //  cerr<<i<<":\n";
        if(a[i]==1){
            if(lft[i]){
                int old=1,New=1;
                for(auto j:splited[lft[i]]){
                    if(lft[i]!=i-1)
                        old=old*binom(j.second+i-lft[i]-1,i-lft[i]-1)%mod;
                    New=New*binom(j.second+i-lft[i],i-lft[i])%mod;
                }
                update(1,1,n,1,lft[i],Time(New*ksm(old,mod-2)%mod));
            }
        }
        else{
            int tail=i-1;
            while(a[tail]==1){
                int bl=1;
                for(auto j:splited[i]){
                    bl=bl*binom(j.second+i-tail,i-tail)%mod;
                }
                update(1,1,n,tail,tail,Time(bl));
                tail--;
            }
            if(lft[i-1]){
                if(a[i-1]==1){
                    int bl=1;
                    for(auto j:splited[lft[i-1]]){
                        bl=bl*binom(j.second+i-lft[i-1]-1,i-lft[i-1]-1)%mod;
                    }
                    bl=ksm(bl,mod-2);
                    for(auto j:splited[lft[i-1]]){
                        int ben=j.second,other=(splited[i].count(j.first)?splited[i][j.first]:0);
                        bl=bl*binom(abs(ben-other)+i-lft[i-1]-1,i-lft[i-1]-1)%mod;
                    }
                    for(auto j:splited[i]){
                        if(!splited[lft[i-1]].count(j.first)){
                            bl=bl*binom(j.second+i-lft[i-1]-1,i-lft[i-1]-1)%mod;
                        }
                    }
                    update(1,1,n,1,lft[i-1],Time(bl));
                }
            }
        }
        if(llim[i]!=1){
            update(1,1,n,1,llim[i]-1,Time(0));
        }
        update(1,1,n,1,i,Sum());
        for(auto j:quarys[i]){
            answer[j.second]=quary(1,1,n,j.first,i)[1];
        }
    }
    for(int i=1;i<=q;i++){
        cout<<answer[i]<<"\n";
    }
}