题目
第一眼看到题目首先想到： 模拟
但直接模拟，边的数量会达到 (r-l+1)\times (r-l) 的量级，显然时空复杂度不达标。
然后我们考虑，最小生成树肯定要求边权最小，而 \operatorname{lcm}(a,b)=\frac{a\times b}{\gcd(a,b)} ，所以自然想到让 gcd(a,b) 尽可能大，也就是让相同的因数尽可能大。
为此，我们枚举这个相同因数 p ，显然这个因数不能 >r ，所以从 2 枚举到 r。
1.然后从 \left \lfloor \frac{l}{p} \right \rfloor \times p 开始枚举到 r，将这之间每个点向有这个因数且在 [l,r] 之间的最小数 \left \lfloor \frac{l}{p} \right \rfloor \times p 连边，权值为 p
2.然后考虑 l 或 \left \lfloor \frac{l}{p} \right \rfloor \times p 及其倍数可能并未与其他的数构成连通图，因此将每个 \left \lfloor \frac{l}{p} \right \rfloor \times p \le r 也做一条连向 l 的边，权值为 \operatorname{lcm}(l,\left \lfloor \frac{l}{p} \right \rfloor \times p) 。
最后跑一遍最小生成树。
因为每个 i\in [l,r] 都被第2个条件与 1 相连，所以这是个连通图。
这个算法的边数就是 \sum^{i=2}_r \frac{r-l}{i} ，根据调和级数，总的为 (r-l)\log_2 r 。
所以总复杂度为 O((r-l)\log^2 (r-l)) 约为 2.7\times 10^7 实际上这个上界很松很松，所以能过。
some code:
init(l, r);
for (int p = 2; p <= ceil(r / l); p++)
{
int u = ceil(1.0 * l / p) * p;
for (int j = u + p; j <= r; j += p)
{
if (rak[j]) //rak用以判断j是否在[l,r]中
g.push_back({u, j, u * j / __gcd(u, j)});
}
if (u <= r)
g.push_back({u, l, u * l / __gcd(u, l)});
}
sort(g.begin(), g.end());
cout << kls();