先考虑离线版本：
LCM可以转化为区间数包含每个 [质因子，所有数含这个质因子个数的最大值] 的乘积，比如区间2，4，8，18质因子2 最多的数是8，有三个，所以2对于LCM的贡献为2^3 = 8. 而3的贡献为3^2 = 9 所以LCM 为：72
所以我们可以考虑枚举右端点r，每次维护一颗线段树，区间[x,r],表示 区间[x,r]的LCM, 而区间[x,r]的值恰好是区间值的乘积。
(因为区间乘积可以用线段树维护，而LCM不行)，显然我们可以这样维护：
添加一个数: ,
枚举每个质因子p，把 pi ^ ci 单点乘到r，这样的话总区间质因子pi的个数就多了ci个，我们需要在前面减去pi使得[x,r]区间质因子p的最大值不会超。
比如：
6 4 8 18
先加入6，线段树各节点的值为：
6 1 1 1
再加入4：
3 4 1 1
再加入8
3 1 8 1
再加入18
1 1 4 18
这样保证了每个枚举的r，区间[l,r]的乘积均为区间[l,r]的LCM， 可以仔细想一下这个过程。
类比线段树离线处理区间种类数，来理解这个做法！
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define re register #define ls (o<<1) #define rs (o<<1|1) //#define m (l+r)/2 #define pb push_back typedef pair<int,int> pii; const double PI= acos(-1.0); const int M = 2e5+7; const int mod = 1e9+7; struct node{ int l,r,id,ans; }p[M]; bool cmp(node a,node b){ return a.r<b.r; } ll qpow(ll a,ll b){ ll ans=1; while(b){ if(b&1)ans=ans*a%mod; a=a*a%mod; b/=2; } return ans; } int m; int prime[M];//第几个质数的值 int id[M];//质数x是第几个质数 int v[M];//i的最小质数 vector<int>pv[M];//数i的质因子 void gao(int n) { for(int i=2;i<=n;i++) { if(v[i]==0)prime[++m]=i,v[i]=i; for(int j=1;j<=m&&i*prime[j]<=n;j++) { v[i*prime[j]]=1; if(i%prime[j]==0)break; } } for(int i=1;i<=m;i++)id[prime[i]]=i; for(int i=1;i<=m;i++) for(int j=prime[i];j<=n;j+=prime[i]) pv[j].pb(prime[i]); } stack<int>s[M];//质数x ，在线段树中出现的位置id int nm[M];//质数x ，到目前为止需要出现多少次 int a[M],ans[M]; ll tr[M<<2];//区间乘积 void bd(int o,int l,int r){ tr[o]=1; if(l==r)return ; int m=(l+r)/2; bd(ls,l,m); bd(rs,m+1,r); } void up(int o,int l,int r,int x,int d){ if(l==r){ tr[o]=tr[o]*d%mod; return ; } int m=(l+r)/2; if(x<=m)up(ls,l,m,x,d); else up(rs,m+1,r,x,d); tr[o]=tr[ls]*tr[rs]%mod; } ll qu(int o,int l,int r,int x,int y){ if(x<=l&&r<=y){ return tr[o]; } int m=(l+r)/2; ll ans=1; if(x<=m)ans=ans*qu(ls,l,m,x,y)%mod; if(y>m)ans=ans*qu(rs,m+1,r,x,y)%mod; return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); gao(200000); int n,q; cin>>n; bd(1,1,n); for(int i=1;i<=n;i++)cin>>a[i]; cin>>m; for(int i=1;i<=m;i++) cin>>p[i].l>>p[i].r,p[i].id=i; sort(p+1,p+1+m,cmp); int sz=1; for(int i=1;i<=n;i++)//枚举右端点 { int tp=a[i],tm=0,tnm=0; for(auto x:pv[a[i]]){ tm=0,tnm=0; while(tp%x==0)tp/=x,tm++; tnm=tm; up(1,1,n,i,qpow(x,tm)); while(!s[x].empty()&&tm){ up(1,1,n,s[x].top(),qpow(x,mod-2)); s[x].pop();tm--; for(int i=1;i<=tnm;i++)s[x].push(i); } } //for(int j=1;j<=n;j++)cout<<qu(1,1,n,j,j)<<" ";cout<<endl; //qu(1,1,n,j,i) --> (j,i) 中所有数的LCM while(p[sz].r==i){ p[sz].ans=qu(1,1,n,p[sz].l,i); sz++; } } for(int i=1;i<=m;i++)ans[p[i].id]=p[i].ans; for(int i=1;i<=m;i++)cout<<ans[i]<<endl; return 0; }
在线的话就是把上述线段树可持久化一下。具体细节看代码即可
比较卡空间。。之前预处理维护质因子空间不够了，其实直接用线性筛质数的V数组即可！！！
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back typedef pair<int,int> pii; const int M = 2e5+7; const int mod = 1e9+7; ll qpow(ll a,ll b){ ll ans=1; while(b){ if(b&1)ans=ans*a%mod; a=a*a%mod; b/=2; } return ans; } int m; int prime[M];//第几个质数的值 int v[M];//i的最小质数 void gao(int n)//预处理1-n每个数的质因子，方便加速后续处理 { for(int i=2;i<=n;i++) { if(v[i]==0)prime[++m]=i,v[i]=i; for(int j=1;j<=m&&i*prime[j]<=n;j++) { v[i*prime[j]]=prime[j]; if(i%prime[j]==0)break; } } } stack<int>s[M];//质数x ，在线段树中出现的位置id int a[M],ans[M]; int rt[M]; //n*logn *logn = 1e5*17*17 2e5 * 200 足够了！ int tr[M*170];//区间乘积 int ls[M*170],rs[M*170],cnt; void bd(int &o,int l,int r){ if(!o)o=++cnt; tr[o]=1; if(l==r)return ; int m=(l+r)/2; bd(ls[o],l,m); bd(rs[o],m+1,r); } //up() void up(int pre,int &o,int l,int r,int x,int d){//可持久化线段树 o=++cnt; tr[o]=tr[pre]; ls[o]=ls[pre]; rs[o]=rs[pre]; tr[o]=(ll)tr[o]*d%mod; if(l==r)return ; int m=(l+r)/2; if(x<=m)up(ls[pre],ls[o],l,m,x,d); else up(rs[pre],rs[o],m+1,r,x,d); } ll qu(int o,int l,int r,int x,int y){ if(x<=l&&r<=y){ return tr[o]; } int m=(l+r)/2; ll ans=1; if(x<=m)ans=ans*qu(ls[o],l,m,x,y)%mod; if(y>m)ans=ans*qu(rs[o],m+1,r,x,y)%mod; return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); gao(200000); int n,q; cin>>n; bd(rt[0],1,n);//先初始化第一颗树，方便后面的树继承 for(int i=1;i<=n;i++)cin>>a[i]; cin>>m; int sz=1; for(int i=1;i<=n;i++){//枚举右端点 rt[i]=rt[i-1];//由于要在当前树上多次更新，我们先把上棵树的根继承过来，然后在这个基础上更新 int tp=a[i],tm=0,tnm=0; while(tp>1){ tm=0,tnm=0; int x=v[tp]; // cout<<tp<<" -- - - "<<x<<endl; while(tp%x==0)tp/=x,tm++; tnm=tm; up(rt[i],rt[i],1,n,i,qpow(x,tm)); while(!s[x].empty()&&tm){ up(rt[i],rt[i],1,n,s[x].top(),qpow(x,mod-2)); s[x].pop();tm--; } for(int j=1;j<=tnm;j++)s[x].push(i); }//qu(1,1,n,j,i) --> (j,i) 中所有数的LCM } int lst=0,l,r; for(int i=1;i<=m;i++){ cin>>l>>r; l=(l+lst)%n+1,r=(r+lst)%n+1; if(l>r)swap(l,r); lst=qu(rt[r],1,n,l,r); cout<<lst<<endl; } return 0; } /* 10 10 2 8 8 8 8 8 10 2 3 10 1 2 6 1 4 10 1 9 9 1 6 10 3 3 8 1 4 10 6 7 */
