题目简述

求 $[L,R]$ 中的数字为点，边权为两端点最小公倍数，生成的图的最小生成树。

验题人做法

有一个最小生成树算法叫 boruvka 算法，过程大概是，初始每个点一个集合，每轮对每个集合找从这个集合出发到另一个集合的最小权值的边，然后每轮合并这 O(集合个数) 条边两端的集合。显然每轮集合个数少至少一半，因此时间复杂度 $O(m\lg n)$，正确性显然。

找每个集合的最小出边就是枚举集合中的点，找最小出边。

对这个题就是，枚举 $x$，考虑他和另一个数字 $y$ 的最小公倍数是 $\frac{xy}{\gcd(x,y)}$。

可以将 $\gcd(x,y)$ 放缩为 $d|\gcd(x,y)$，即枚举 $d|x$，在所有满足 $d|y$ 的 $y$ 中找最小的（且来自不同集合的）。

如果不限制来自不同集合就直接记录即可，要求来自不同集合的简单处理方法就是对每个 $d\in[1,R]$ 记录是 $d$ 的倍数的数中，最小的那个（及其来自哪个集合），以及和最小值来自不同的集合的次小值（及其来自哪个集合）即可。