选拔赛4

原题来自THUPC2022

对于一个无向完全图G=(V,E)，点u与点v的边权为u,v的最小公倍数lcm(u,v).称G的最小生成树为V的最小公倍树.

现在给出L,R,请你给出V=L,L+1,...,R的最小公倍树LCT(V).

输入仅一行，包括两个正整数L,R(1≤L,R≤106,0≤R−L≤105)

输出一个正整数，表示LCT(V)的边权和。

L=3，R=5形成的无向完全图如下：

最小公倍树由边(3,4),(3,5)组成

这题所有的边数太多了，我们需要考虑哪些边是可能用得上的。

正确做法是枚举因子（设为k），对于因子k来说，找到第一个>=L的数x，再将x与(L,R]区间中其他为x的倍数的数（设为y）建边，边权为x*y/k（QWQ具体为啥是这样的我没法解释清楚，以后有时间了可能会去证明，这题我自己一开始的想法就是暴力建边，拿了11分）

贴一下正确代码