题目链接
题目大意：
给你nnn个数，
每次往第iii个数里面里面乘aaa，问你这nnn个数的LCM\text{LCM}LCM是多少？
解题思路：
多个数的lcm不是所有数的乘积除以所有数的gcd，如 4 8 3
正确求法是每个数分解质因数后求区间每个质因子的最大幂次
做法：由于每个数的范围在2e52e52e5内，不可能存下所有质因子
但是！
对于大于2e5\sqrt{2e5}2e5的质因子，对于每一个数而言要么数量为000，要么为111对于小于2e5\sqrt{2e5}2e5的质数，只有87个
解法1：主席树 + RMQ（卡空间）
对于上面小于2e5\sqrt{2e5}2e5的质数我们对每个质数都开个rmqrmqrmq：里面是每个位置的幂次最大值对于大于2e5\sqrt{2e5}2e5的质因子，我们开个主席树里面的叶子节点是位置，对于每个root[R]root[R]root[R],然后对于同一个质数，我们维护它出现的最右边的位置，因为你固定了RRR之后,对于同一个质因子贡献只能算一次，那么我们肯定是要最靠右边的位置，你要查询[L,R][L,R][L,R]的时候直接跑以root[R]root[R]root[R]为根的子树，然后在里面区间查询[L,R][L,R][L,R]就好了然后结果就是两部分相乘解法2: 主席树
首先我们知道上面有个技巧就是把在固定了RRR之后我们把贡献算到了最后一次出现的位置那么我们看看对于RMQRMQRMQ的部分能不能套进行求解？我们知道在固定了RRR之后，对于同一个质因子的如果指数大的出现在右边，那么指数比它小并且在它左边的贡献就不算了。就是可以覆盖掉但是如果有指数比它小的并且出现在在它的右边？那该怎么办？那么我们就可以把一部分的贡献拖过去如下图假如我们这里有个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]);// 防止被重复除，每次只除一个jRight[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;}
