题意

有一个序列 $a\{n\}$，$m$ 次询问，查询区间 $[l,r]$ 的 $lcm \bmod 10^9 + 7$。

分析

什么友好的出题人求 $lcm$ 还取模呀！

容易发现，求 $lcm$ 与取模不太兼容，我们只能考虑维护一些奇怪的东西。我们考虑质因数分解，然后对于每个质因数维护区间最大值。但是质因数个数会很多，我们要用到经典定理，一个数至多只有一个质因数大于 $\sqrt{n}$，并且这道题 $a_i \le 2 \times 10^5$，稍微算一下就知道有 $86$ 个质因数小于 $\sqrt{n}$。这一部分我们可以用 ST 表直接维护。剩下就是直接用主席树维护 lcm。

#include <bits/stdc++.h>
using namespace std;
#define il inline
#define N 100005
#define V 448
static char buf[100000], *pa = buf, *pd = buf;
#define gc pa == pd && (pd = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pd) ? EOF : *pa++
inline int rd() {
    register int x(0); register char c(gc);
    while (c < '0' || c > '9') c = gc;
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = gc;
    return x;
}
const int P = 1e9 + 7;
int n, m, a[N], pt[87], l, r, lst[N << 1], pr[N], cnp, lans;
int ls[N << 6], rs[N << 6], rt[N], ep, tr[N << 6];
short lg[N];
bool isp[450];
int ksm(int x, int r){
    int ans = 1;
    while (r){
        if (r & 1) ans = 1ll * ans * x % P;
        x = 1ll * x * x % P, r >>= 1;
    }return ans;
}
struct ST{
    char f[N][18];
    il void init(int op){
        for (int j = 1; j <= 17; j++)
            for (int i = 1; i + (1 << j) - 1 <= n; i++)
                f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
    }
    il int maxk(int l, int r){
        short p = lg[r - l + 1];
        return max(f[l][p], f[r - (1 << p) + 1][p]);
    }
}st[87];
void add(int &p, int l, int r, int x, int k){
    ep++;
    if (!tr[p]) tr[p] = 1;
    tr[ep] = 1ll * tr[p] * k % P, ls[ep] = ls[p], rs[ep] = rs[p], p = ep;
    if (l == r) return ;
    int mid = (l + r) >> 1;
    if (x <= mid) add(ls[p], l, mid, x, k);
    else add(rs[p], mid + 1, r, x, k);
}
int ask(int p, int l, int r, int nl, int nr){
    if (!p) return 1;
    if (nl <= l && r <= nr) return tr[p];
    int mid = (l + r) >> 1, ans = 1;
    if (nl <= mid) ans = ask(ls[p], l, mid, nl, nr) % P;
    if (nr > mid) ans = ans * 1ll * ask(rs[p], mid + 1, r, nl, nr) % P;
    return ans;
}
int main(){
    n = rd();
    for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= n; i++) a[i] = rd();
    for (int i = 2; i <= V; i++){
        if (!isp[i]){
            pr[++cnp] = i;
            for (int j = i + i; j <= V; j += i) isp[j] = 1;
        }
    }
    for (int i = 1; i <= n; i++){
        int x = a[i];
        for (int j = 1; pr[j] <= x && j <= cnp; j++){
            int c = 0;
            while (x % pr[j] == 0) x /= pr[j], c++;
            st[j].f[i][0] = c;
        }
        rt[i] = rt[i - 1];
        if (x > 1) add(rt[i], 0, n - 1, lst[x], x), lst[x] = i;
    }
    for (int i = 1; i <= cnp; i++) st[i].init(i);
    m = rd();
    while (m--){
        l = (rd() + lans) % n + 1, r = (rd() + lans) % n + 1;
        if (l > r) swap(l, r);
        int res = 1;
        for (int i = 1; i <= cnp; i++) res = 1ll * res * ksm(pr[i], st[i].maxk(l, r)) % P;
        res = 1ll * res * ask(rt[r], 0, n - 1, 0, l - 1) % P * ksm(ask(rt[l - 1], 0, n - 1, 0, l - 1), P - 2) % P;
        printf ("%d\n", lans = (res % P));
    }
    return 0;
}