【拆贡献】CF1422F Boring Queries

考虑质因数分解，我们求区间的 \(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;
}