题目
长度为n(n<=1e5)的数组a[]，ai在[1,2e5]之间，
q(q<=1e5)个询问，每次给出[l,r]，询问[l,r]区间内的ai的lcm，
本题强制在线
思路来源
ustze、Heltion代码
题解
强制在线，n=1e5，所以用主席树，
主席树直接维护区间乘积，所以要将lcm引起的乘积变小的部分预先除掉，
询问[l,r]的时候，直接回答r为右端点的主席树在[l,r]的区间乘积
考虑lcm，对于每个质因子p来说，若区间内有两个含p的数，则
lcm应该是几个有这个质因子的数的出现次数最大值，
类似询问区间mex以及可持久化结构的一些套路，让每个值的出现位置尽可能靠右
此处需要维护质因子使其尽可能靠右，具体来说
此处为主席树root[3]的维护过程，
对于每个p的幂次，都维护一个其出现的最右的位置，
只让蓝色的区域在lcm中有贡献，此为代码1
而代码2，则是维护了一个栈，栈中放入(质因子的位置，当前还剩的幂次)
如果当前最右可以与左侧的比它小的幂次抵消，则尽可能抵消，
然后将当前最右的幂次放入栈中
代码1
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,mod=1e9+7;
typedef pair<int,int> P;
#define fi first
#define se second
int n,q,x,y,l,r,lasans;
int a[N],inv[N];
//空间 log(2e5)质因子个数*log(1e5)一条链*n 18*17*1e5
int root[N],ls[200*N],rs[200*N],lcm[200*N],mxp[N],rig[N],c;
vector<P>p[N],now[N];
int modpow(int x,int n,int mod){
int res=1;
for(;n;n>>=1,x=1ll*x*x%mod){
if(n&1)res=1ll*res*x%mod;
}
return res;
}
void upd(int l,int r,int &cur,int las,int pos,int v){
cur=++c;
ls[cur]=ls[las];rs[cur]=rs[las];
lcm[cur]=1ll*lcm[las]*v%mod;
if(l==r){
return;
}
int mid=(l+r)/2;
if(pos<=mid)upd(l,mid,ls[cur],ls[las],pos,v);
else upd(mid+1,r,rs[cur],rs[las],pos,v);
}
int ask(int cur,int l,int r,int ql,int qr){
if(!cur){
return 1;
}
if(ql<=l && r<=qr){
return lcm[cur];
}
int mid=(l+r)/2,res=1;
if(ql<=mid)res=1ll*res*ask(ls[cur],l,mid,ql,qr)%mod;
if(qr>mid)res=1ll*res*ask(rs[cur],mid+1,r,ql,qr)%mod;
return res;
}
int main(){
inv[1]=1;
lcm[0]=1;
for(int i=2;i<N;++i){
inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
if(!mxp[i]){
for(int j=i;j<N;j+=i){
mxp[j]=i;
}
}
}
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
root[i]=root[i-1];
for(int v=a[i];v!=1;){
int x=v,pc=1;
while(x%mxp[v]==0){
x/=mxp[v];
pc*=mxp[v];
if(rig[pc]){
upd(1,n,root[i],root[i],rig[pc],inv[mxp[v]]);
}
rig[pc]=i;
}
upd(1,n,root[i],root[i],rig[pc],pc);
v=x;
}
}
scanf("%d",&q);
while(q--){
scanf("%d%d",&x,&y);
l=(lasans+x)%n+1;r=(lasans+y)%n+1;
if(l>r)swap(l,r);
printf("%d\n",lasans=ask(root[r],1,n,l,r));
}
return 0;
}
代码2
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,mod=1e9+7;
typedef pair<int,int> P;
#define fi first
#define se second
int n,q,x,y,l,r,lasans;
int a[N],inv[N];
int root[N],ls[200*N],rs[200*N],lcm[200*N],c;
vector<P>p[N],now[N];
int modpow(int x,int n,int mod){
int res=1;
for(;n;n>>=1,x=1ll*x*x%mod){
if(n&1)res=1ll*res*x%mod;
}
return res;
}
void upd(int l,int r,int &cur,int las,int pos,int v){
cur=++c;
ls[cur]=ls[las];rs[cur]=rs[las];
lcm[cur]=1ll*lcm[las]*v%mod;
if(l==r){
return;
}
int mid=(l+r)/2;
if(pos<=mid)upd(l,mid,ls[cur],ls[las],pos,v);
else upd(mid+1,r,rs[cur],rs[las],pos,v);
}
int ask(int cur,int l,int r,int ql,int qr){
if(!cur){
return 1;
}
if(ql<=l && r<=qr){
return lcm[cur];
}
int mid=(l+r)/2,res=1;
if(ql<=mid)res=1ll*res*ask(ls[cur],l,mid,ql,qr)%mod;
if(qr>mid)res=1ll*res*ask(rs[cur],mid+1,r,ql,qr)%mod;
return res;
}
int main(){
inv[1]=1;
lcm[0]=1;
for(int i=2;i<N;++i){
inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
if(p[i].empty()){
for(int j=i;j<N;j+=i){
int num=0;
for(int k=j;k%i==0;k/=i){
num++;
}
p[j].push_back(P(i,num));
}
}
}
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
root[i]=root[i-1];
for(auto x:p[a[i]]){
int v=x.fi,cnt=x.se,lef=cnt;
while(!now[v].empty() && lef){
int h=min(now[v].back().se,lef);
lef-=h;now[v].back().se-=h;
upd(1,n,root[i],root[i],now[v].back().fi,modpow(inv[v],h,mod));
if(now[v].back().se==0){
now[v].pop_back();
}
}
if(cnt){
upd(1,n,root[i],root[i],i,modpow(v,cnt,mod));
now[v].push_back(P(i,cnt));
}
}
}
scanf("%d",&q);
while(q--){
scanf("%d%d",&x,&y);
l=(lasans+x)%n+1;r=(lasans+y)%n+1;
if(l>r)swap(l,r);
printf("%d\n",lasans=ask(root[r],1,n,l,r));
}
return 0;
}
