一、题目重述

给定长度为 $n$ 的数组 $a$，以及 $q$ 个在线查询。
每个查询给出 $x, y$，计算：

$$l = (\text{last} + x) \bmod n + 1,\quad r = (\text{last} + y) \bmod n + 1 $$

若 $l > r$ 则交换。然后输出区间 $[l, r]$ 的 LCM，对 $10^9+7$ 取模。
其中 $\text{last}$ 是上一个查询的答案（初始为 $0$）。

数据范围：$n, q \le 10^5$，$a_i \le 2\times 10^5$。

---

二、LCM 与质因数分解

设 $a_i$ 的质因数分解为：

$$a_i = \prod_{p \text{ prime}} p^{e_p(i)}$$

则区间 $[l, r]$ 的 LCM 为：

$$\mathrm{LCM}(a_l, \dots, a_r) = \prod_{p \text{ prime}} p^{\max_{i \in [l,r]} e_p(i)} $$

即对每个质数 $p$，取区间内所有 $a_i$ 中 $p$ 的指数的最大值，然后乘起来。

---

三、问题转化

我们需要支持：

• 在线查询区间 $[l, r]$ 的 LCM
• 无法离线排序（因为 $l, r$ 依赖于上一个答案）

核心难点：LCM 对每个质数独立，但区间查询时如何快速知道每个质数的最大指数？

---

四、关键性质

对于固定质数 $p$，考虑数组 $b_i = e_p(a_i)$（$p$ 的指数）。
区间 $[l, r]$ 内 $p$ 的最大指数，可以通过维护每个位置作为左端点时的最大值来得到，但直接维护很困难。

重要观察：
如果某个位置 $i$ 有 $p^k$ 的因子，那么对于所有 $l \le i$，$[l, r]$ 的 LCM 中 $p$ 的指数至少是 $k$。
但实际上，我们只关心最后一次出现的更大指数。

更经典的转化（主席树标准做法）：

• 从左到右扫描数组，对每个右端点 $r$，维护一个数组 $f_r[l]$ 表示 $[l, r]$ 的 LCM。
• 当 $r$ 增加 $1$ 时，对于 $a_{r+1}$ 的每个质因子 $p^k$，我们需要将 $p^k$ 乘入所有 $l \le r+1$ 的 $f_{r+1}[l]$ 中。
• 但 $p^k$ 可能之前出现过，如果之前位置 $pos$ 也有 $p$ 的因子，那么 $p^k$ 只对 $l > pos$ 有贡献（因为对于 $l \le pos$，最大值已经被之前的 $p$ 的指数覆盖）。

因此，我们可以：

• 对每个质数 $p$，维护它上一次出现的位置 last[p]
• 当扫描到 $i$ 时，对于 $a_i$ 的每个质因子 $p^k$：
  • 如果 last[p] 存在，则在 last[p] 位置除以 $p^k$（即乘 $p^{-k}$）
  • 在当前位置 $i$ 乘以 $p^k$
• 这样，对每个右端点 $r$，$f_r[l]$ 就是 $l$ 到 $r$ 的 LCM。

---

五、数据结构：主席树

由于我们需要对每个 $r$ 保存一个数组 $f_r[l]$，并且 $r$ 最大 $10^5$，直接存储 $O(n^2)$ 不行。

使用可持久化线段树（主席树）：

• 每个版本 $r$ 对应一棵线段树，叶子 $l$ 存储 $f_r[l]$（即 $[l, r]$ 的 LCM）
• 版本 $r$ 从版本 $r-1$ 继承，并应用上述“除和乘”的更新
• 更新是单点修改（对位置 last[p] 和 $i$ 分别修改）

查询时，直接在第 $r$ 棵线段树中查询区间 $[l, r]$ 的乘积即可。

---

六、算法步骤

1. 预处理：线性筛求 $[1, 2\times10^5]$ 内每个数的最小质因子 minPrime。
2. 预处理逆元：因为需要乘 $p^{-k}$，提前计算每个 $p^k$ 的逆元。
3. 主席树构建：
   • root[0] 为空树（所有位置值为 $1$）
   • 对 $i = 1$ 到 $n$：
     • root[i] = root[i-1]
     • 分解 $a_i$，对每个质因子 $p$ 及其指数 $cnt$：
       • 令 $val = p^{cnt}$
       • 如果 last[p] != 0，则在 root[i] 中将位置 last[p] 乘以 $val^{-1}$（即除以 $val$）
       • 在 root[i] 中将位置 $i$ 乘以 $val$
       • 更新 last[p] = i
4. 在线查询：
   • 读入 $x, y$，计算 $l, r$
   • 答案 = 在第 $r$ 棵线段树中查询区间 $[l, r]$ 的乘积
   • 更新 last_ans

---

七、复杂度分析

• 线性筛：$O(M \log \log M)$，$M = 2\times10^5$
• 每个 $a_i$ 的质因子分解：$O(\log a_i)$
• 主席树：每个质因子更新两次（除和乘），总节点数 $O(n \log n \cdot \text{因子数})$，约 $n \log n \times 6$（每个数最多 $6$ 个不同质因子），可接受
• 查询：$O(\log n)$
• 总复杂度：$O((n + q) \log n + n \log M)$

---

八、最终代码（标程）

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
const int M = 2e5 + 5;
const int MOD = 1e9 + 7;

int n, q;
int a[N];
int last[M];
int inv[M];
int root[N];
int minPrime[M];

vector<int> primes;

int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1LL * res * a % MOD;
        a = 1LL * a * a % MOD;
        b >>= 1;
    }
    return res;
}

void sieve() {
    for (int i = 2; i < M; ++i) {
        if (minPrime[i] == 0) {
            minPrime[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (p > minPrime[i] || i * p >= M) break;
            minPrime[i * p] = p;
        }
    }
}

// 主席树节点
struct Node {
    int lc, rc, val;
} tr[N * 200];
int tot = 0;

int build(int l, int r) {
    int u = ++tot;
    tr[u].val = 1;
    if (l == r) return u;
    int mid = (l + r) >> 1;
    tr[u].lc = build(l, mid);
    tr[u].rc = build(mid + 1, r);
    return u;
}

int update(int pre, int l, int r, int pos, int mul) {
    int u = ++tot;
    tr[u] = tr[pre];
    tr[u].val = 1LL * tr[pre].val * mul % MOD;
    if (l == r) return u;
    int mid = (l + r) >> 1;
    if (pos <= mid) tr[u].lc = update(tr[pre].lc, l, mid, pos, mul);
    else tr[u].rc = update(tr[pre].rc, mid + 1, r, pos, mul);
    return u;
}

int query(int u, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tr[u].val;
    int mid = (l + r) >> 1;
    int res = 1;
    if (ql <= mid) res = 1LL * res * query(tr[u].lc, l, mid, ql, qr) % MOD;
    if (qr > mid) res = 1LL * res * query(tr[u].rc, mid + 1, r, ql, qr) % MOD;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    sieve();
    
    // 预处理逆元
    for (int i = 1; i < M; ++i) {
        inv[i] = qpow(i, MOD - 2);
    }
    
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    
    root[0] = build(1, n);
    
    for (int i = 1; i <= n; ++i) {
        root[i] = root[i - 1];
        int x = a[i];
        while (x > 1) {
            int p = minPrime[x];
            int cnt = 0;
            int val = 1;
            while (x % p == 0) {
                x /= p;
                cnt++;
                val = 1LL * val * p % MOD;
            }
            if (last[p]) {
                root[i] = update(root[i], 1, n, last[p], inv[val]);
            }
            root[i] = update(root[i], 1, n, i, val);
            last[p] = i;
        }
    }
    
    cin >> q;
    int last_ans = 0;
    while (q--) {
        int x, y;
        cin >> x >> y;
        int l = (last_ans + x) % n + 1;
        int r = (last_ans + y) % n + 1;
        if (l > r) swap(l, r);
        last_ans = query(root[r], 1, n, l, r);
        cout << last_ans << "\n";
    }
    
    return 0;
}

---

九、正确性总结

• 利用 LCM 对质数的独立性，将问题转化为对每个质数维护区间最大指数
• 使用“最近出现位置”技巧，将更新限制在常数次
• 主席树支持在线查询和可持久化，完美解决强制在线问题