自动搬运

查看原文

来自洛谷，原作者为

	摸鱼酱 喜欢就值得。

搬运于2025-08-24 22:33:06，当前版本为作者最后更新于2021-08-10 15:37:55，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

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

$1\leq n\leq 10^5$，$1\leq a_i\leq 10^7$。

朴素地找边显然有 $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$，显然有前者不小于后者，于是完成了证明。