自动搬运

查看原文

来自洛谷，原作者为

	Renshey 滚落沙尘，泛生浮光。掠影千年，奔走四方。

搬运于2025-08-24 22:45:00，当前版本为作者最后更新于2023-02-11 18:51:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

记 $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;
}