题目链接

---

题目大意：

给你$n$个数，
每次往第$i$个数里面里面乘$a$，问你这$n$个数的$\text{LCM}$是多少？

---

解题思路：

多个数的lcm不是所有数的乘积除以所有数的gcd，如 4 8 3
正确求法是每个数分解质因数后求区间每个质因子的最大幂次
做法：由于每个数的范围在$2e5$内，不可能存下所有质因子
但是！

1. 对于大于$\sqrt{2e5}$的质因子，对于每一个数而言要么数量为$0$，要么为$1$
2. 对于小于$\sqrt{2e5}$的质数，只有87个

解法1：主席树 + RMQ（卡空间）

1. 对于上面小于$\sqrt{2e5}$的质数我们对每个质数都开个$rmq$：里面是每个位置的幂次最大值
2. 对于大于$\sqrt{2e5}$的质因子，我们开个主席树里面的叶子节点是位置，对于每个$root[R]$,然后对于同一个质数，我们维护它出现的最右边的位置，因为你固定了$R$之后,对于同一个质因子贡献只能算一次，那么我们肯定是要最靠右边的位置，你要查询$[L,R]$的时候直接跑以$root[R]$为根的子树，然后在里面区间查询$[L,R]$就好了
3. 然后结果就是两部分相乘

解法2: 主席树

1. 首先我们知道上面有个技巧就是把在固定了$R$之后我们把贡献算到了最后一次出现的位置
2. 那么我们看看对于$RMQ$的部分能不能套进行求解？
3. 我们知道在固定了$R$之后，对于同一个质因子的如果指数大的出现在右边，那么指数比它小并且在它左边的贡献就不算了。就是可以覆盖掉
4. 但是如果有指数比它小的并且出现在在它的右边？那该怎么办？
5. 那么我们就可以把一部分的贡献拖过去
6. 如下图假如我们这里有个5次方的因子（5个方格）后面要3次方的因子
   
   
   贡献转移
   具体实现细节见代码：

---

ACcode

#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define Lson rt << 1, l , mid
#define Rson rt << 1|1, mid + 1, r
#define ms(a,al) memset(a,al,sizeof(a))
#define log2(a) log(a)/log(2)
#define lowbit(x) ((-x) & x)
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INF 0x3f3f3f3f
#define LLF 0x3f3f3f3f3f3f3f3f
#define f first
#define s second
#define endl '\n'
using namespace std;
const int N = 2e6 + 10, mod = 1e9 + 7;
const int maxn = 200010;
const long double eps = 1e-5;
const int EPS = 500 * 500;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<int,int> PLL;
typedef pair<double,double> PDD;
template<typename T> void read(T &x) {x = 0;char ch = getchar();int f = 1;while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {read(first);read(args...);
}
int n, m, tot;
int Right[maxn];
struct Segtree {int lson, rson;int lcm;
}sgt[maxn * 200];
int root[maxn];
inline void insert(int &now, int last, int l, int r, int pos, int val) {now = ++ tot;sgt[now] = sgt[last];sgt[now].lcm = (1ll * sgt[now].lcm * val) % mod;if(l == r) return;if(pos <= mid) insert(sgt[now].lson,sgt[last].lson,l,mid,pos,val);else insert(sgt[now].rson,sgt[last].rson,mid+1,r,pos,val);
}inline int ask(int now, int l, int r, int ql, int qr) {if(!now) return 1;if(ql <= l && qr >= r) return sgt[now].lcm;int res = 1;if(ql <= mid) res = (1ll * res * ask(sgt[now].lson,l,mid,ql,qr)) % mod;if(qr > mid) res = (1ll * res * ask(sgt[now].rson,mid+1,r,ql,qr)) % mod;return res;
}int inv[maxn];
inline void init() {inv[1]=1;sgt[0].lcm=1; for(int i = 2; i < 2e5 + 10; ++ i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
}int main() {init();read(n);for(int i = 1; i <= n; ++ i) {int x;cin >> x;root[i] = root[i-1];for(int j = 2; 1ll * j * j <= x; ++ j) {int px = 1;while(x % j == 0) {x /= j;px *= j;if(Right[px]) // 每个值上次出现的最右边的位置insert(root[i],root[i],1,n,Right[px],inv[j]);	// 防止被重复除，每次只除一个j	Right[px] = i;}if(px != 1)insert(root[i],root[i],1,n,Right[px],px);}if(x > 1) {if(Right[x]) insert(root[i],root[i],1,n,Right[x],inv[x]);insert(root[i],root[i],1,n,i,x);Right[x] = i;}}read(m);int last = 0;for(int i = 1; i <= m; ++ i) {int u, v;read(u,v);int l, r;l = (last + u) % n + 1;r = (last + v) % n + 1;if(l > r) swap(l,r);cout << (last = ask(root[r],1,n,l,r) % mod) << endl;}return 0;
}