做完这道题大大提升了我对主席树的认知。
· 传送门:here
给定一个长度为 \(n\) 的序列 \(a\) 以及 \(q\) 次询问 。
每次询问包含 \(2\) 个整数 \(l,r\) ，你需要求出区间 \([l,r]\) 的最小公倍数对 \(10^9 + 7\) 取模的结果。
询问强制在线 。
数据范围：
\(1\leq n,q\leq 10^5,1 \leq a_i\leq 2\cdot 10^5,1\leq x,y \leq 10^5\)
知识点：
1.主席树
2.一点点的数论
Part1：原理
我们可以先弱化原问题，将它转为离线
众所周知，最小公倍数=上一个公倍数*当前的数/重复因数
离线就好办了，不妨回忆起一道题：HH的项链
这道题，我们不也是离线后，只取最后面的数作为基准量，再消掉前一个数吗？
思路有了：
1.把问题按r端点排序
2.解决到当前问题[l,r]的时候保证在数r的因子不重复 把前面与r相同次数的因子全部消了 这样保证了最小公倍数
3.查询：在r时查找[l,r]的积
这就是一个线段树的板子了，和HH的项链思路一样。
可是要求强制在线，不妨举例子思考一下。
e.g.
\(2,3,5\) ----> \(2,3,5\)
\(6,4,12\) ----> \(3*2,2*2,2*2*3\)
以2为视角：次数为 1-->2-->2
考虑在r时的情况：
1.上一个公倍数是已知的
2.处理与当前重复的质因数，保证当前质因数的合法
可以开个pos数组 记录一下现在出现过没有这个数的x次方
把以前有的乘个逆元消了就行
e.g.
- \(6,4,12\) ----> \(3*2,2*2,2*2*3\)
- \(st\)---------> \(3*2\)
- \(nxt\)--------> \(3*2*inv[2],2*2\)
- \(nxt\)--------> \(3*2*inv[2]*inv[3],2*2*inv[2]*inv[2] ,2*2*3\)
这样我们就可以发现
在到第r个版本时，我们保证sum[r]是包含所有真因子的
即一定保证r出现的所有因子前面一定乘了逆元消了
那么，求l的时候往前一查漏掉的因子就行
其实就是区间查
比如上面例子。
当我们查询(2,3)时，我们需要跳到3号版本，查询：
\((2*2*inv[2]*inv[2]) *(2*2*3)\)
询问历史版本+单点修改，区间查询
这样问题就从线段树变成主席树的板子了
为什么要跳到r版本呢？结合一下离线操作就明白了。
Part2 算法步骤：
1.预处理每个数的最小因子 O(nlln)
2.处理每个数因子数和加入历史版本 O(nlog^2n)
3.从历史版本r查询 O(mlogn)
复杂度分析：
时间复杂度O(\(nlog^2n\))
空间复杂度 一个点log级别因数 加入log次 是\(nlog^2n\)的
But出题人十分毒瘤 卡空间 开longlong会炸 记得用强制转换(\(1ll\))
Part3 Code:
#include<bits/stdc++.h>
#define ll long long
#define MAXN 100005
#define MAXM 200005
using namespace std;
int n,m,a[MAXN],f[MAXM],pos[MAXM],root[MAXN];
int last;
int inv[MAXM],mod=(1e9)+7;
int cnt;
struct tree{
int v;
int l,r;
}tr[MAXN*400];
int clone(int x)
{
tr[++cnt]=tr[x];
return cnt;
}
int updata(int now,int l,int r,int x,ll v)
{
now=clone(now);
tr[now].v=1ll*tr[now].v*v%mod;
if(l==r) return now;
int mid=(l+r)/2;
if(x<=mid) tr[now].l=updata(tr[now].l,l,mid,x,v);
else tr[now].r=updata(tr[now].r,mid+1,r,x,v);
return now;
}
int query(int now,int l,int r,int x)
{
if(r<x) return 1;
if(l>=x) return tr[now].v;
int mid=(l+r)/2;
return 1ll*query(tr[now].l,l,mid,x)*query(tr[now].r,mid+1,r,x)%mod;
}
void init()
{
tr[0].v=1;
for(int i=2;i<=MAXM-5;i++)
{
if(f[i]) continue;
for(int j=i;j<=MAXM-5;j+=i)
f[j]=i;
}
inv[1]=1;
for(int i=2;i<=MAXM-5;i++)
inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
}
int main()
{
init();
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
int div,t=1;
root[i]=root[i-1];
while(a[i]!=1)
{
div=f[a[i]];
t=1;
while(a[i]%div==0)
{
t*=div;
a[i]/=div;
if(pos[t]) root[i]=updata(root[i],1,n,pos[t],inv[div]);
pos[t]=i;
}
root[i]=updata(root[i],1,n,i,t);
}
}
scanf("%d",&m);
while(m--)
{
int l,r;
scanf("%d%d",&l,&r);
l=(l+last)%n+1;
r=(r+last)%n+1;
if(l>r) swap(l,r);
last=query(root[r],1,n,l);
printf("%d\n",last);
}
return 0;
}