考虑质因数分解，我们求区间的 \(lcm\) 就是 \(\prod a_i\) 除以一些东西。
不难发现如果算 \(x^k \in lcm\) 那么我们只能算一次，那么我们直接把这个东西挂在前一个出现的位置即可。
使用主席树维护即可。这个题，很难。
// LUOGU_RID: 123092767
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i ++)
#define per(i, r, l) for (int i = r; i >= l; i --)
#define cpy(x, y, s) memcpy(x, y, sizeof(x[0]) * (s))
#define mem(x, k) memset(x, k, sizeof(x))
#define ll long long
// \yhx-12243/ 鱼大保佑！！
using namespace std;
const int _ = 2e5 + 5, mod = 1e9 + 7;
int M = 2e5;
int pr[_], inv[_];
int n, q, a[_], ocr[_];
int power (int x, int y) {
int res = 1;
for ( ; y; y >>= 1, x = 1ll * x * x % mod)
if (y & 1) res = 1ll * res * x % mod;
return res;
}
int tot, rt[_];
int lc[_ * 200], rc[_ * 200], prod[_ * 200];
void clone (int & x, int p, int v) {
x = ++ tot;
lc[x] = lc[p], rc[x] = rc[p], prod[x] = 1ll * prod[p] * v % mod;
}
void modify (int & x, int prv, int l, int r, int p, int v) {
clone(x, prv, v);
if (l == r) return ;
int mid = (l + r) >> 1;
if (p <= mid) modify(lc[x], lc[prv], l, mid, p, v);
else modify(rc[x], rc[prv], mid + 1, r, p, v);
}
int query (int x, int l, int r, int ql, int qr) {
if (! x) return 1;
if (ql <= l && r <= qr) return prod[x];
int mid = (l + r) >> 1, res = 1;
if (ql <= mid) res = 1ll * res * query(lc[x], l, mid, ql, qr) % mod;
if (qr > mid) res = 1ll * res * query(rc[x], mid + 1, r, ql, qr) % mod;
return res;
}
int main () {
rep(i, 2, M) {
inv[i] = power(i, mod - 2);
if (! pr[i]) {
for (int x = i; x <= M; x += i) pr[x] = i;
}
}
prod[0] = 1, inv[1] = 1;
cin >> n;
rep(i, 1, n) scanf("%d", & a[i]);
rep(i, 1, n) {
int x = a[i];
modify(rt[i], rt[i - 1], 1, n, i, x);
while (pr[x]) {
int k = pr[x], t = 1;
while (x % k == 0) {
x /= k, t *= k;
if (ocr[t]) {
int root = rt[i];
modify(rt[i], root, 1, n, ocr[t], inv[k]);
}
ocr[t] = i;
}
}
}
cin >> q;
int lst = 0;
rep(i, 1, q) {
int l, r;
scanf("%d%d", & l, & r);
l = (l + lst) % n + 1, r = (r + lst) % n + 1;
if (l > r) swap(l, r);
printf("%d\n", lst = query(rt[r], 1, n, l, r));
}
return 0;
}