1900D - Small GCD

给定序列 \(A\)，定义 \(f(a, b, c)\) 为 \(a, b, c\) 中最小的次小的数的 \(\gcd\)，求：

\[\sum_{i = 1}^n \sum_{j = i + 1}^n \sum_{k = j + 1}^n f(a_i, a_j, a_k) \]

题解

目前来说有两种方法，都十分有启发意义，但是有共同的开头。

考虑到 \(A\) 的顺序实际上没有什么关系，那么可以先对 \(A\) 排序，使得 \(i < j < k \iff a_i \le a_j \le a_k\)，那么此时 \(f(a_i, a_j, a_k) = \gcd(a_i, a_j)\)，从而答案的式子转化为：

\[\sum_{i = 1}^n \sum_{j = i + 1}^n \gcd(a_i, a_j) \times (n - j) \]

接下来衍生出了两种做法。

莫比乌斯反演

准确来说应该是欧拉反演？

注意到：

\[\sum_{d | x} \varphi(d) = x \]

那么我们可以将目标表达式写为：

\[\sum_{i = 1}^n \sum_{j = i + 1}^n \sum_{d | a_i, a_j} \varphi(d) \times (n - j) \]

交换求和顺序，可以得到：

\[\begin{aligned} & \sum_{d = 1}^V \varphi(d) \sum_{i = 1}^n \sum_{j = i + 1}^n [d | a_i] [d | a_j] (n - j) \\ = & \sum_{d = 1}^V \varphi(d) \sum_{j = 1}^n (n - j) [d | a_j] \sum_{i = 1}^{j - 1} [d | a_i] \end{aligned} \]

考虑对于每一个 \(d\)，我们将满足 \(d | a_i\) 的数提出来作为集合 \(S\)，那么这是容易 \(O(|S|)\) 求解的。

接下来我们只需要考虑其复杂度了。

注意到可以认为 \(\tau(n) = O(\sqrt n)\)（在本题值域限制中 \(\tau(n) \le 128\)）也就是说每一个数至多在 \(128\) 个 \(S\) 中出现，那么我们可以知道 \(\sum |S| = O(128n)\)，于是复杂度是合理的。

\(\tau(n)\) 表示 \(n\) 的因数个数。

提前预处理一下因数的分解，这是 \(O(V \log V)\) 的（由于值域很小，可以直接保存），以及 \(\varphi\) 即可。

总复杂度是 \(O(V \log V + 128n + n \log n)\)。

另类的枚举

回到基础的式子：

\[\sum_{i = 1}^n \sum_{j = i + 1}^n \gcd(a_i, a_j) \times (n - j) \]

如果我们固定 \(j\)，发现 \(\gcd(a_i, a_j)\) 一定是 \(a_j\) 的因数，并且 \(a_j\) 的因数至多有 \(128\) 个，这启发我们可以直接枚举 \(d = \gcd(a_i, a_j)\) 来算 \(d \times cnt_j \times (n - j)\)。

考虑 \(cnt_j\) 该如何计算，可以开一个桶 \(but_x\) 记录有多少个满足 \(x | a_i\) 的数。

发现并不能简单的 \(cnt_j = but_d\)，因为这样会算重，考虑将会算重的部分给去掉。

具体来说，发现如果满足 \(d | \gcd(a_i, a_j)\)，那么 \(x | d \to x | \gcd(a_i, a_j)\)，也就是说 \(d\) 会在其所有因数再算一次。直接容斥有点麻烦，所以考虑直接在 \(but\) 上进行修改，也就是说进行 \(z | d, but_z \leftarrow but_z - but_d\) 的操作。