CF1422F Boring Queries
Mobius127
2021-11-03 13:09:13
[题传](https://www.luogu.com.cn/problem/CF1422F)
简化题意：在线区间 $\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 的项链 ](https://www.luogu.com.cn/problem/P1972) 这题的在线做法，用主席树，每次把上一次出现的 $b$ 拔掉即可，空间复杂度 $O(n \log n)$，时间复杂度 $O((n+q) \log n)$。
大概算了一下 ST 表空间会被卡，改成 `char` 类即可。
```cpp
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;
}
```