THUPC2022初赛 A.最小公倍树 解题报告
THUPC2022 A.最小公倍树
给定一个点编号在 [L,R] 范围内的完全图,边 (u,v) 的权值为 \mathrm{lcm}(u, v),请你求出这张图的最小生成树权值和.
L,R \leq 10^6,R - L \leq 10^5
Kruskal 优化建图.
观察到如果直接建图的时间复杂度是 \mathcal{O}((R-L)^2 ) 的,无法接受.但是发现在这个过程中,有很多边实际上是可以省略的,接下来来发掘一下这些边的性质.
首先我们有
\mathrm{lcm}(u, v) = \frac{u\times v}{\mathrm{gcd}(u,v)}
这实