CF1422F Boring Queries

Mobius127 · 2021-11-03 13:09:13 · 题解

题传

简化题意：在线区间 \operatorname{lcm}。

显然不能直接上线段树，因为 \operatorname{lcm} 只增不减，在这种情况下直接开高精都是不可行的，(10^5 个 10^8 级别的数乘起来稳定飞天)，所以我们考虑分开算每个质因子的贡献。

设素数集 P=\{p_1, p_2, \dots p_m \}，则序列中的数 a_i 可表示成：

\prod_{j=1}^m p_j^{c_{i, j}}

记 C_j =\max_{i=l}^r c_{i, j}，

那么根据定义，区间最小公倍数为：

\prod_{j=1}^m p_j^{C_j}

大眼观察 Max_{a}=2 \times 10^5，由于任何数只会有一个大于 \sqrt{Max_{a}} \approx 450 的素数，打表后发现这个范围内只有 87 个素数，显然根号分治了：

对于 \le 450 的质因子，预处理 ST 表，每次询问暴力枚举质因子，空间复杂度 O(87 n \log n)，时间复杂度 O(87n+87 \log \log n + 87q)。
对于大于 \ge 450 的质因子，由于只有一个，令 b_i 为 a_i 的最大值因子，那么就是求区间内不同种类数的乘积，类似于 HH 的项链这题的在线做法，用主席树，每次把上一次出现的 b 拔掉即可，空间复杂度 O(n \log n)，时间复杂度 O((n+q) \log n)。

大概算了一下 ST 表空间会被卡，改成 char 类即可。

const int mo=1e9+7;
const int N=1e5+5;
const int R=450;
const int Pcnt=87;
int Su[Pcnt]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449};
int n, m, Lg[N], a[N], pre[N*2], root[N], Mi[Pcnt][18];
char f[Pcnt][N][18];
namespace ZQF_AKIOI_LH_AKCTSC_CHT_AKWC{
    int tot;
    struct node{int pro, lc, rc;}d[N*40];
    #define ls d[k].lc
    #define rs d[k].rc
    #define mid (l+r>>1)
    void pushup(int k){d[k].pro=1ll*d[ls].pro*d[rs].pro%mo;}
    void build(int &k, int l, int r){
        k=++tot;d[k].pro=1;
        if(l==r){d[k].pro=a[l&r];return ;}
        build(ls, l, mid), build(rs, mid+1, r);
        pushup(k);
    }
    void insert(int &k, int l, int r, int x, int v){
        d[++tot]=d[k];k=tot;
        if(l==r){d[k].pro=v;return ;}
        if(x<=mid) insert(ls, l, mid, x, v);
        else insert(rs, mid+1, r, x, v);
        pushup(k);
    }
    int query(int k, int l, int r, int x, int y){
        if((!k)||l>y||r<x) return 1;
        if(x<=l&&r<=y) return d[k].pro;
        return 1ll*query(ls, l, mid, x, y)*query(rs, mid+1, r, x, y)%mo;
    }
    #undef ls
    #undef rs
    #undef mid
}
int query(int j, int l, int r){
    int k=Lg[r-l+1];
    return max(f[j][l][k], f[j][r-(1<<k)+1][k]);
}
signed main(){
    n=read();Lg[0]=-1;
    for(int i=1; i<=n; i++){
        a[i]=read();Lg[i]=Lg[i>>1]+1;
        for(int j=0; j<Pcnt; j++)
            while(a[i]%Su[j]==0) f[j][i][0]++, a[i]/=Su[j];
    }
    ZQF_AKIOI_LH_AKCTSC_CHT_AKWC :: build(root[0], 1, n);
    for(int i=1; i<=n; i++){
        root[i]=root[i-1];if(a[i]==1) continue;
        if(pre[a[i]]) ZQF_AKIOI_LH_AKCTSC_CHT_AKWC :: insert(root[i], 1, n, pre[a[i]], 1);
        pre[a[i]]=i;
    }
    for(int k=0; k<Pcnt; k++){
        for(int j=1; j<18; j++)
            for(int i=1; i+(1<<j)-1<=n; i++)
                f[k][i][j]=max(f[k][i][j-1], f[k][i+(1<<j-1)][j-1]);
        Mi[k][0]=1;
        for(int i=1; i<18; i++) Mi[k][i]=1ll*Mi[k][i-1]*Su[k]%mo;
    }
    m=read();int last=0;
    for(int i=1; i<=m; i++){
        int l=(read()%n+last%n)%n+1, r=(read()%n+last%n)%n+1;if(l>r) swap(l, r);last=1;
        for(int j=0; j<Pcnt; j++){
            int x=query(j, l, r);
            last=1ll*last*Mi[j][x]%mo;
        }
        last=1ll*last*(ZQF_AKIOI_LH_AKCTSC_CHT_AKWC :: query(root[r], 1, n, l, r))%mo;
        printf("%d\n", last);
    }
    return 0;
}