纪念我场上速通还爆标但死于模数没改的模拟赛。（CF594D）

· · 题解

传送门

这里是跑满的单 \log 做法。纪念我场切还爆标但是死于模数没改的模拟赛。

首先考虑双 \log 怎么做。我们有众所周知的结论：根据唯一分解定理，我们设 x=\sum_{i=1}^{s}p_i^{k_i}，那么有 \varphi(x)=x\times \prod_{i=1}^{s}\frac{p_i-1}{p_i}。换句话说，我们只要求出区间内含有哪些种类的质因子就容易求出答案。

那么考虑 离线询问 + 扫描线 + 线段树（这里可以树状数组，常数更小），将询问挂在右端点上再从左往右扫，维护每个质因子将其贡献（就是 \frac{p_i-1}{p_i}）乘到最后一次出现的位置上，那么每次询问只需要区间求乘积即可。质因子分解容易线性筛预处理做到 \log V，于是总时间复杂度 O(n\log n\log V)。

其实优化掉 \log V 是简单的。我们考虑到一个 1e6 范围的数，其较大的质因子非常少，那么考虑将前 31 个质因子用一个 int 压缩起来，然后求一下区间或（这里采用 ST 表 O(1) 求）即可考虑完这些质因子。剩下的大质因子则不会超过 2 个，那么这部分继续用上述 扫描线 + 树状数组 即可。

综上，我们通过压位直接将树状数组修改次数压缩到了 O(n) 级别，平衡了复杂度。于是 O((n+q)\times 31+(n+q)\log n) 的做法出现了，而且扩展到强制在线套上主席树也不会爆空间！当然，由于前者跑满了所以实际上不一定跑得过某些实现优秀的双 \log（）

code

#include <bits/stdc++.h>
//#include <windows.h>
//taskkill /f /im 未命名1.exe
#define ED cerr<<endl;
#define TS cerr<<"I AK IOI"<<endl;
#define cr(x) cerr<<x<<endl;
#define cr2(x,y) cerr<<x<<" "<<y<<endl;
#define cr3(x,y,z) cerr<<x<<" "<<y<<" "<<z<<endl;
#define cr4(x,y,z,w) cerr<<x<<" "<<y<<" "<<z<<" "<<w<<endl;
#define pr(a,l,r) for(int i=l;i<=r;++i) cerr<<a[i]<<' ';ED
#define popcnt __builtin_popcount
#define all(s) s.begin(),s.end()
#define bstring basic_string
//#define add(x,y) (x+=y)%=mod
#define pii pair<int,int>
#define epb emplace_back
#define pb push_back
#define mk make_pair
#define ins insert
#define fi first
#define se second
#define ll long long
//#define ull unsigned long long
using namespace std;
const int N=2e5+5,M=1e6+5,INF=2e9,mod=1e9+7;
int t,n,m;
ll inv[M],a[N],b[N],ans[N];
int st[20][N];vector<int> big[N];
int primes[M],id[M],vis[M],pre[M],len=0;

ll qpow(ll x,int y=mod-2) {
    ll res=1;
    while(y) {
        if(y&1) res=res*x%mod;
        x=x*x%mod,y>>=1;
    }
    return res;
}

struct que {
    int l,r,id;

    bool operator<(const que &W) const {
        return r<W.r;
    }
}q[N];

void init(ll n) {
    for(int i=2;i<=n;++i) {
        if(!vis[i]) {
            id[i]=len,primes[len++]=i;
            pre[i]=i;
        }
        for(int j=0;j<len&&primes[j]<=n/i;++j) {
            vis[i*primes[j]]=1;
            pre[i*primes[j]]=primes[j];
            if(i%primes[j]==0) break;
        }
    }
    inv[1]=1;
    for(int i=2;i<=n;++i) {
        inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    }
}

ll tr[N];int ps[M];

void add(int u,ll x) {
    for(int i=u;i<=n;i+=i&(-i)) tr[i]=tr[i]*x%mod;
}

ll query(int u) {
    ll res=1;
    for(int i=u;i!=0;i-=i&(-i)) res=res*tr[i]%mod;
    return res; 
}

int query2(int l,int r) {
    int k=__lg(r-l+1);
    return st[k][l]|st[k][r-(1<<k)+1];
}

int main()
{
    scanf("%d",&n);ll mx=0;b[0]=1;
    for(int i=1;i<=n;++i) {
        scanf("%lld",&a[i]);
        mx=max(mx,a[i]),b[i]=b[i-1]*a[i]%mod;
        tr[i]=1;
    }
    init(mx);
    for(int i=1;i<=n;++i) {
        int x=a[i];
        while(x>1) {
            if(id[pre[x]]<31) st[0][i]|=(1<<id[pre[x]]);
            else big[i].epb(pre[x]);
            x/=pre[x];
        }
    }
    for(int i=1;i<20;++i) {
        for(int j=1;j<=n-(1<<i)+1;++j) {
            st[i][j]=st[i-1][j]|st[i-1][j+(1<<i-1)];
        }
    }
    scanf("%d",&m);
    for(int i=1;i<=m;++i) {
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id=i;
    }
    sort(q+1,q+1+m);
    for(int i=1,j=1;i<=n;++i) {
        for(auto it:big[i]) {
            if(ps[it]) add(ps[it],it*inv[it-1]%mod);
            ps[it]=i,add(i,(it-1)*inv[it]%mod);
        }
        while(j<=m&&q[j].r==i) {
            int l=q[j].l,r=q[j].r,s=query2(l,r);
            ll res=b[r]*qpow(b[l-1])%mod;
            for(int k=0;k<31;++k) {
                if((s>>k)&1) {
                    res=res*(primes[k]-1)%mod*inv[primes[k]]%mod;
                }
            }
            res=res*query(r)%mod*qpow(query(l-1))%mod;
            ans[q[j].id]=res,++j;
        }
    }
    for(int i=1;i<=m;++i) {
        printf("%lld\n",ans[i]);
    }
    return 0;
}