A. 最小公倍树

时间限制： 1.0 秒

空间限制： 512 MiB

相关文件： 题目目录

题目背景

听说有人嫌题面描述都太长了。

题目描述

对于任意 $V\subset\mathbb{N}^*$，$|V|<+\infty$，构造一张无向完全图 $G=(V,E)$，其中 $(u, v)$ 的边权为 $u,v$ 的最小公倍数 $\mathrm{lcm}(u, v)$。称 $G$ 的最小生成树为 $V$ 的最小公倍树（LCT, Lowest Common Tree）。

现在给出 $L, R$，请你求出 $V={L, L+1, \cdots, R}$ 的最小公倍树 $LCT(V)$。

输入格式

从标准输入读入数据。

输入仅一行，包括两个正整数 $L, R$。

输出格式

输出到标准输出。

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

样例1输入

3 12

样例1输出

样例2输入

1	6022 14076

样例2输出

1	66140507445

样例3输入

1	13063 77883

样例3输出

1	3692727018161

样例4输入

1	325735 425533

样例4输出

1	1483175252352926

子任务

对于 $100%$ 的数据，保证 $1\le L\le R\le 10^6$，且 $R-L\le 10^5$。

可以直观感受到这个东西肯定和因数和倍数有关系，我们考虑对于这个东西进行考虑。

发现 $R - L \le 10^5$ 那么可以带 $\log $，我们考虑对于区间范围内的所有数考虑其因子会产生的贡献，对于相同的因子进行连边，但是发现这里的边数还是平方级别的，我们尝试使用 $\tt prim$ 进行更新，也就是我们需要快速找到和已知集合连边的最小边权。

考虑加入一个点 $x$ 加入之后的贡献，我们考虑其所有的因子，进行更新集合内是当前因子倍数的最小值，集合外同理。考虑集合内部开桶，集合外因为会修改直接开链表即可，同时更新一下涉及因子的 $\tt lcm$，之后考虑直接线段树暴力维护全局 $\tt lcm$ 最小值，复杂度是 $O(n \sqrt n \log n)$，其中 $n = 10^5$ 差不多能过。

$\tt Update$：

事实上复杂度其实完全不用那么高，我之前复杂度比较高的原因主要是在于因子的复杂度，然而我们可以考虑将质因子全部拿出来之后再进行 $\tt dfs$ 组合，这样复杂度就是 $O(\log n)$ 的。

加上我们的数据结构维护复杂度可以做到 $O(n \log^2 n )$。