P7789.

· · 题解

给定序列 a_{1\cdots n}，生成一张 n 个点的无向完全图，i,j 之间的边权为 \min\{a_i\bmod a_j,a_j\bmod a_i\}，求最小生成树。

朴素地找边显然有 $O(n^2)$ 条，考虑实际是否真的有这么多有效边。 首先对于所有权值去重，相同权值的默认是同一个点，记 $m=\max\{a_i\}$。 对于每一个权值 $x$，我们可以去枚举它的倍数 $d$，找到值在 $[dx,(d+1)x)$ 内最小的数，记为一条有效边，特殊地，$d=1$ 时范围为 $(x,2x)$。 因为值域很小，找数这个操作可以放到桶里，从后往前扫一遍得到。 于是这样会找到 $O(m\ln m)$ 条边，找到之后桶排做 Kruskal，就可以做到 $O(m\ln m·\alpha(n))$，如果只有这些有效边，复杂度和空间都是可以接受的。 考虑如何证明这样一定不劣，假设一个点 $a$ 连向的不是某个倍数区间里第一个数 $b$，而是靠后一些的 $c$，显然有 $c>b>a,b\bmod a< c\bmod a$，我们考虑把 $a-c$ 改为 $a-b-c$，新的花费是 $c\bmod b+b\bmod a$，原本的花费是 $c\bmod a$，设 $\lfloor \frac ca\rfloor =\lfloor \frac ba\rfloor=d$，则有原来的花费为 $c-d·a$，新的花费为 $c-b·\lfloor\frac cb\rfloor +b-d·a$，显然有前者不小于后者，于是完成了证明。