当前位置：首页 > news >正文

公约数距

news 2026/3/27 21:13:39

公约数距

定义一个整数序列 $B=(B_1,B_2,\dots,B_k)$ 的分数为 $\sum_{i=1}^{k} \sum_{j=1}^{i-1} \gcd (B_i,B_j) \times 2^{(i-j-1)}$。

给出一个整数序列 $A=(A_1,A_2,\dots,A_N)$，求出以下问题在 $m=1,2,\dots,N$ 时的答案：

序列 $A=(A_1,A_2,\dots,A_m)$ 的分数，对 $998244353$ 取模后的值。

输入描述:

第一行包含两个整数 $n, q \left( 1\le N\le 5 \times 10^5 \right)$，表示数组的长度和询问的个数。

第二行包含 $n$ 个整数，表示数组 $A \left( 1\le A_i\le 10^5 \right)$。

输出描述:

输出 $N$ 行，第 $i$ 行表示当 $m=i$ 时的答案。

示例1

输入

3
9 6 4

输出

0 3 7

示例2

输入

5
3 8 12 6 9

输出

0 1 11 33 70

示例3

输入

10
47718 21994 74148 76721 98917 73766 29598 59035 69293 29127

输出

0 2 16 23 62 543 823 950 1661 3864

备注:

数据范围

$1\le N\le 5 \times 10^5$
$1\le A_i\le 10^5$
输入的值全部为整数。

解题思路

赛时用的暴力做法，结果跑得很快，可能是数据比较弱。

先简单讲一下暴力的做法。把式子解耦得到 $\sum\limits_{i=1}^{m}{2^{i-1} \sum\limits_{j=1}^{i-1}{\gcd (a_i,a_j) \cdot 2^{-j}}}$。当 $i$ 固定时，$\gcd(a_i,a_j)$ 的结果必然是 $a_i$ 的约数，因此我们可以枚举 $a_i$ 的所有约数 $d$，然后查看前面满足 $d \mid a_j$ 的 $a_j$，其对答案的贡献为 $d \cdot 2^{i-j-1}$。然而，这种方法存在问题：实际上，只有当 $d$ 恰好等于 $\gcd(a_i,a_j)$ 时，$a_j$ 才对答案有贡献。而由于 $\gcd(a_i,a_j)$ 的约数 $d$ 也满足 $d \mid a_j$，这会导致额外错误的贡献。

具体来说，按照上述方法计算贡献时，实际上每个 $a_j$ 对答案的贡献应为 $\sum\limits_{d \mid \gcd(a_i, a_j)}{d \cdot 2^{i-j-1}}$，但我们只需要 $\gcd(a_i,a_j) \cdot 2^{i-j-1}$。

为了避免计入这些额外的贡献，我们可以从大到小枚举 $a_i$ 的约数 $d$，此时，当某个 $a_j$ 第一次满足 $d \mid a_j$ 时，这个 $d$ 一定是 $a_i$ 与 $a_j$ 的最大公约数 $\gcd(a_i,a_j)$。为了防止在之后的枚举过程中，$d \mid a_j$ 再次导致额外贡献被统计，我们可以将 $a_j$ 从前面删除。在具体操作之前，我们还需要思考如何在枚举到 $d$ 时，快速知道前面哪些 $a_j$ 满足 $d \mid a_j$，并计算它们对答案的贡献。

很简单，只需可以开一个数组 $s_d$ 来表示含约数 $d$ 的 $a_i$ 关于 $2^{-i}$ 的总和。当枚举完 $a_i$ 后，枚举其所有约数 $d$，然后更新 $s_d \gets s_d + 2^{-i}$。这样，当枚举到 $d$ 时，$s_d$ 就是满足 $d \mid a_j$ 且没有被删除的 $a_j$ 对应的 $2^{-j}$ 总和。由于这些 $a_j$ 是第一次被枚举到，之后的删除操作就是对每个 $a_j$ 枚举其所有约数 $d$，然后 $s_d \gets s_d - 2^{-j}$。这样，下次遇到满足 $d \mid a_j$ 的情况时，$a_j$ 就不会对答案产生额外贡献。

因此，这种方法是十分暴力的，需要枚举 $a_i$ 所有约数的所有约数，计算量为 $\sum\limits_{x \mid a_i}{d(x)}$，其中 $d(x)$ 表示 $x$ 的约数个数。复杂度的上限是 $O(n A^{\frac{2}{3}})$，但通过剪枝（即当 $s_d = 0$ 时跳过 $d$ 的约数枚举）可以减少计算量，因此在实际运行中速度较快。

AC 代码如下，时间复杂度为 $O(n A^{\frac{2}{3}})$：

#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 5e5 + 5, M = 1e5 + 5, mod = 998244353;int a[N], inv[N];
vector<int> ds[M];
int s[M], c[M];int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;inv[0] = 1;for (int i = 1; i <= n; i++) {cin >> a[i];inv[i] = 1ll * inv[i - 1] * 499122177 % mod;}for (int i = M - 1; i; i--) {for (int j = i; j < M; j += i) {ds[j].push_back(i);}}for (int i = 1, sum = 0, p = 1; i <= n; i++) {for (auto &x : ds[a[i]]) {int t = (s[x] - c[x] + mod) % mod;if (!t) continue;sum = (sum + 1ll * x * p % mod * t) % mod;for (auto &y : ds[x]) {c[y] = (c[y] + t) % mod;}}for (auto &x : ds[a[i]]) {s[x] = (s[x] + inv[i]) % mod;c[x] = 0;}p = 2 * p % mod;cout << sum << ' ';}return 0;
}

下面给出正解。官方题解给出的做法很跳跃，至少我是不可能想不到的，可以先当作是结论来记。比如遇到 $\gcd(a_i,a_j)$ 可以尝试代入 $\gcd(a_i,a_j) = \sum\limits_{d \mid \gcd(a_i,a_j)}{\varphi(d)}$。

首先需要知道关于欧拉函数的一个性质：$n = \sum\limits_{d \mid n}{\varphi(d)}$。证明也很难想到。设 $f(d)$ 为满足 $\gcd(k,n) = d$ 的 $k$ 的数量，其中 $1\leq k \leq n$。那么有 $n = \sum\limits_{d \mid n}{f(d)}$。而 $\gcd(k,n) = d$ 等价于 $\gcd\left( \frac{k}{d},\frac{n}{d} \right) = 1$，因此 $f(d)$ 就变成了与 $\frac{n}{d}$ 互质的 $k \left( 1 \leq k \leq \frac{n}{d} \right)$ 的个数，即 $f(d) = \varphi\left( \frac{n}{d} \right)$。因此，$n = \sum\limits_{d \mid n}{\varphi\left( \frac{n}{d} \right)} = \sum\limits_{d \mid n}{\varphi(d)}$（这是因为约数 $d$ 与 $\frac{n}{d}$ 具有对称性）。

将 $\gcd(a_i, a_j) = \sum\limits_{d \mid \gcd(a_i, a_j)}{\varphi(d)}$ 代入 $\sum\limits_{i=1}^{m}{2^{i-1} \sum\limits_{j=1}^{i-1}{\gcd(a_i, a_j) 2^{-j}}}$，得到 $$\sum\limits_{i=1}^{m}{2^{i-1} \sum\limits_{j=1}^{i-1}{2^{-j} \sum\limits_{d \mid \gcd(a_i, a_j)}{\varphi(d)}}} = \sum\limits_{i=1}^{m}{2^{i-1} \sum\limits_{d \mid a_i}{\varphi(d)} \sum\limits_{j=1}^{i-1}{2^{-j}[d \mid a_j]}}$$

左边式子中的 $d$ 是 $a_i$ 和 $a_j$ 的公约数，右边则是交换求和顺序后的结果。为了快速计算 $\sum\limits_{j=1}^{i-1}{2^{-j}[d \mid a_j]}$ 这部分的结果，我们可以使用和暴力方法类似的方式，开一个数组 $s_d$ 表示含约数 $d$ 的 $a_i$ 关于 $2^{-i}$ 的总和。当枚举完 $a_i$ 后，枚举其所有约数 $d$，然后更新 $s_d \gets s_d + 2^{-i}$。但在这里，我们不需要进行删除操作。

AC 代码如下，时间复杂度为 $O(n \sqrt[3]{A})$：

#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 5e5 + 5, M = 1e5 + 5, mod = 998244353;int a[N];
int prime[M], phi[M], cnt;
bool vis[M];
vector<int> ds[M];
int s[M];void init() {phi[1] = 1;for (int i = 2; i < M; i++) {if (!vis[i]) {prime[cnt++] = i;phi[i] = i - 1;}for (int j = 0; prime[j] * i < M; j++) {vis[prime[j] * i] = true;if (i % prime[j] == 0) {phi[prime[j] * i] = phi[i] * prime[j];break;}phi[prime[j] * i] = phi[i] * (prime[j] - 1);}}for (int i = 1; i < M; i++) {for (int j = i; j < M; j += i) {ds[j].push_back(i);}}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;for (int i = 0; i < n; i++) {cin >> a[i];}init();for (int i = 0, p = 1, inv = 1, sum = 0; i < n; i++) {inv = inv * 499122177ll % mod;for (auto &x : ds[a[i]]) {sum = (sum + 1ll * p * phi[x] % mod * s[x]) % mod;s[x] = (s[x] + inv) % mod;}p = 2 * p % mod;cout << sum << ' ';}return 0;
}