【题解】P9060

· · 题解

记 w = \max\{a_i\}。

考虑计算每个素数的贡献。对素数按 \sqrt w 分类，则每个 a_i 仅包含至多一个 > \sqrt w 的素因子。

对于素数 p \le \sqrt w，设区间中有 k 个 p 的倍数，则 \gcd 为 p 倍数的非空子集有 2^k - 1 个。对于 p^2, p^3, \dots，可以在先前的基础上增量计算贡献，同样也为 p^{2^k-1}。因此可以通过预处理 p^1, p^2, p^4, \dots, p^{2^n} 与 p^{-1}，快速计算每次询问的答案。不难证明素数幂的个数是 O(\sqrt w) 级别的，因此该部分的时间复杂度为 O((n+m)\sqrt w)。可以通过离线做到 O(n + m + w) 的空间复杂度。

对于素数 p > \sqrt w，不同的 p 的总出现次数不超过 n，可以同上预处理出 p^1, p^2, p^4, \dots。查询时需要查询区间中 p 的倍数的个数，可以直接莫队解决。该部分的时间复杂度为 O(n\sqrt m)，空间复杂度为 O(n + m)。

综上，可以在 O(n \sqrt w + m\sqrt w + n \sqrt m) 的时间复杂度，O(n + m + w) 的空间复杂度内完成本题。

代码：

#include <bits/stdc++.h>
#define Getchar() p1 == p2 and (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++
char buf[1 << 21], *p1, *p2;
int read (void)
{
    int x = 0; char c = Getchar();
    while (c < '0' or c > '9') c = Getchar();
    while (c >= '0' and c <= '9') x = x * 10 + c - 48, c = Getchar();
    return x;
}
const int maxn = 1 << 17;
const int mod = 998244353;
int n, m, a[maxn], S, pos[maxn], ans[maxn], res_pow = 1, res_inv = 1;
int M, B, pr[maxn], tot, inv[maxn], Pow[maxn], sum[maxn];
int cnt[maxn], vec[maxn], L[maxn], C;
struct query {int l, r, id;} q[maxn];
int sqr (int x) {return 1LL * x * x % mod;}
int power (int x, int y)
{
    int z = 1;
    for (; y; y >>= 1, x = 1LL * x * x % mod) if (y & 1) z = 1LL * z * x % mod;
    return z;
}
void sieve (int B)
{
    std::vector<int> vis(B + 1, 0);
    for (int i = 2; i <= B; i++) if (!vis[i])
    {
        pr[++tot] = i;
        for (int j = i; j <= B; j += i) vis[j] = 1;
    }
}
void add (int w) {if (w > 1) res_pow = 1LL * res_pow * vec[L[w] + (cnt[w]++)] % mod;}
void del (int w) {if (w > 1) res_inv = 1LL * res_inv * vec[L[w] + (--cnt[w])] % mod;}
signed main ()
{
    n = read(); m = read(); S = n / sqrt(m);
    for (int i = 1; i <= n; i++) M = std::max(M, a[i] = read()), pos[i] = (i - 1) / S + 1;
    sieve(B = sqrt(M)); inv[0] = inv[1] = 1;
    for (int i = 2; i <= M; i++) inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;
    for (int i = 1; i <= m; i++) q[i].l = read(), q[i].r = read(), q[i].id = i, ans[i] = 1;
    for (int i = 1; i <= tot; i++)
    {
        Pow[0] = pr[i];
        for (int j = 1; j <= n; j++) Pow[j] = sqr(Pow[j - 1]);
        for (int j = pr[i]; j <= M; j *= pr[i])
        {
            for (int k = 1; k <= n; k++) sum[k] = sum[k - 1] + (a[k] % j == 0);
            for (int k = 1; k <= m; k++) ans[k] = 1LL * ans[k] * Pow[sum[q[k].r] - sum[q[k].l - 1]] % mod * inv[pr[i]] % mod;
        }
        for (int j = 1; j <= n; j++) while (a[j] % pr[i] == 0) a[j] /= pr[i];
    }
    for (int i = 1; i <= n; i++) if (a[i] > 1) cnt[a[i]]++;
    for (int i = 1; i <= M; i++) if (cnt[i])
    {
        vec[L[i] = ++C] = i;
        for (int j = 1; j < cnt[i]; j++) ++C, vec[C] = sqr(vec[C - 1]);
    }
    for (int i = 1; i <= M; i++) cnt[i] = 0;
    std::sort(q + 1, q + m + 1, [] (const query &q1, const query &q2) {return pos[q1.l] == pos[q2.l] ? q1.r < q2.r : q1.l < q2.l;});
    for (int i = 1, l = 1, r = 0; i <= m; i++)
    {
        while (l > q[i].l) add(a[--l]);
        while (r < q[i].r) add(a[++r]);
        while (l < q[i].l) del(a[l++]);
        while (r > q[i].r) del(a[r--]);
        ans[q[i].id] = 1LL * ans[q[i].id] * res_pow % mod * power(res_inv, mod - 2) % mod;
    }
    for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
    return 0;
}