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$ 的操作。
注意需要还原 $but$
于是就不需要容斥了……接着分析复杂度。
枚举因数同上，是 $O(128n)$ 的，然而我们多了一个修改桶的操作，发现与枚举所有数的因数的复杂度是类同的，所以是 $O(m \log m)$ 的。
怎么感觉复杂度假了？
总复杂度就是 $O(128n + m \log m + n \log n)$，差不多。
总结
我首先想到的就是第一种做法……QwQ，数学学多了，但是仍然想了比较长的时间，基础还是不太牢。
第二种做法相对来说要亲民一些，但是比较难拓展到其他题上，也没法析出新的模型（因为完全可以被第一种方法取代），所以说第二种方法惜败。
最后再回顾一下莫反的 $5$ 个经典套路：
- $[x = 1] = \sum_{d | x} \mu(d)$
- $x = \sum_{d | x} \varphi(d)$
- 整除分块
- 枚举 $\gcd$
- 枚举 $T = kd$