题目链接：Codeforces 594D

今天的数学课上，老师告诉 Vovochka 正整数的欧拉函数 $\varphi(n)$ 是计算小于等于 $n$ 且与 $n$ 互质的正整数的函数，$1$ 和任意正整数互质所以 $\varphi(1)=1$。

现在老师给了 Vovochka 一个数列 $a_1,a_2,\dots,a_n$，要求回答 $q$ 个询问 $l_i,r_i$，计算 $\varphi\left(\prod_{i=l}^r a_i\right)$ 的值，答案对 $10^9 + 7$ 取模。这个问题对二年级学生来说太难了，所以你决定帮助 Vovochka。

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

Solution

由于只有询问操作，因此我们首先想到离线后用莫队解决。但是莫队的复杂度为 $\mathcal O(q\sqrt n\log a_i)$（其中 $\log a_i$ 指每个数的本质不同的质因子个数），显然无法通过本题（我卡了半个小时常数还是 $\text{TLE}$ 出题人毒瘤）。

还是考虑离线，我们将询问按照右端点排序，维护一个右指针，将每个 $a_i$ 逐个加入。用树状数组维护每个位置对答案的贡献。

我们考虑 $a_i$ 的其中一个质因子 $p$（其他的质因子同理）。由于我们把询问按照右端点排序了，而每个质因子只能对答案有一次贡献，那么我们把 $p$ 的贡献放到区间 $[1,i]$ 的最右边，即进行操作 $\text{add}(i, p - 1)$ 和 $\text{add}(i, p ^ {-1})$。如果 $p$ 已经出现过了，那么我们需要防止区间左端点左侧产生贡献，维护一个 $last_i$ 表示 $i$ 这个质因子上次出现的位置，将 $last_p$ 位置的贡献消去即可。

对于如何快速分解每个数的质因子，我们可以根据线性筛的本质：每个数只会被其最小质因子筛去，在筛的过程中直接记录每个数的最小质因子即可！

时间复杂度：$\mathcal O((n + q) \log n \log a_i)$。

Code

#include <cstdio>
#include <algorithm>

const int N = 2e5 + 5, M = 1e6 + 5;
const int P = 1e9 + 7;

int n, m, tot, a[N], b[N], p[M / 10], f[M], pre[N], lst[M], ans[N];
bool flg[M];

struct Data {
    int l, r, idx;
    bool operator<(const Data &b) const {
        return r < b.r;
    }
} q[N];

void sieve(int n) {
    for (int i = 2; i <= n; i++) {
        if (!flg[i]) {
            p[++tot] = i, f[i] = i;
        }
        for (int j = 1; j <= tot && i * p[j] <= n; j++) {
            flg[i * p[j]] = true, f[i * p[j]] = p[j];
            if (i % p[j] == 0) break;
        }
    }
}
int pow(int x, int p) {
    int ans = 1;
    for (; p; p >>= 1, x = 1LL * x * x % P) {
        if (p & 1) ans = 1LL * ans * x % P;
    }
    return ans;
}
int inv(int x) {
    return pow(x, P - 2);
}
void add(int x, int v) {
    for (; x <= n; x += x & -x) b[x] = 1LL * b[x] * v % P;
}
int query(int x) {
    int ans = 1;
    for(; x; x ^= x & -x) ans = 1LL * ans * b[x] % P;
    return ans;
}
void update(int i) {
    for (int x = a[i], p = f[x]; x > 1; p = f[x]) {
        add(i, p - 1), add(i, inv(p));
        if (lst[p]) add(lst[p], inv(p - 1)), add(lst[p], p);
        lst[p] = i;
        while (x % p == 0) x /= p;
    }
}
int main() {
    scanf("%d", &n);
    pre[0] = 1;
    int mx = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        mx = std::max(mx, a[i]);
        pre[i] = 1LL * pre[i - 1] * a[i] % P;
    }
    sieve(mx);
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].idx = i;
    }
    std::sort(q + 1, q + m + 1);
    for (int i = 0; i <= n; i++) b[i] = 1;
    for (int i = 1, j = 0; i <= m; i++) {
        int x = q[i].l, y = q[i].r;
        while (j < y) update(++j);
        ans[q[i].idx] = 1LL * pre[y] * inv(pre[x - 1]) % P * query(y) % P * inv(query(x - 1)) % P;
    }
    for (int i = 1; i <= m; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}