题目概述

本题要求构造区间 $[L, R]$ 内所有整数作为顶点的完全图，其中边 $(u, v)$ 的边权为 $\mathrm{lcm}(u, v)$，求该图的最小生成树的边权和。

数据范围：$1 \le L \le R \le 10^6$，且 $R - L \le 10^5$

算法思路

核心观察

直接构建完全图会有 $O((R-L)^2)$ 条边，无法承受。需要利用数论性质减少候选边数量。

关键性质：对于任意 $u, v$，$\mathrm{lcm}(u, v) \ge \max(u, v)$，且当 $v$ 是 $u$ 的倍数时，$\mathrm{lcm}(u, v) = v$，这是可能的最小边权。

算法设计

核心思想：枚举因子 + Kruskal算法

1. 候选边生成策略

对于每个因子 $i$，考虑区间 $[L, R]$ 内所有 $i$ 的倍数：

• 设 $nl = \lceil \frac{L}{i} \rceil$，$nr = \lfloor \frac{R}{i} \rfloor$
• 对于 $j = nl, nl+1, \ldots, nr$，$x = j \times i$ 是 $i$ 的倍数且在区间内
• 连接这些倍数之间的边，边权为 $\mathrm{lcm}(x, y)$

2. 状态设计

• UnionFind数据结构：维护连通分量
• 边集合：存储候选边 $(u, v, w)$，其中 $w = \mathrm{lcm}(u, v)$

关键操作详解

候选边生成

for (int i = 1; i <= r; ++i) {
    int nl = (l + i - 1) / i, nr = r / i;
    ll x = nl * i;
    
    for (int j = nl + 1; j <= nr; ++j) {
        ll y = (ll)j * i;
        es.emplace_back(lcm(x, y), x, y);
    }
}

状态分析：

• 外层循环枚举所有可能的因子 $i$
• 内层循环枚举 $i$ 在区间 $[L, R]$ 内的所有倍数
• 对于每对倍数 $(x, y)$，计算 $\mathrm{lcm}(x, y)$ 作为边权

Kruskal算法执行

ranges::sort(es);  // 按边权排序

ll ans = 0;
UnionFind uf(r + 1);

for (auto [w, u, v] : es) {
    if (uf.unite(u, v))
        ans += w;
}

算法正确性证明

候选边完备性

定理：最小生成树的所有边都在生成的候选边集合中。

证明思路：

1. 考虑最小生成树中的任意边 $(u, v)$
2. 设 $d = \gcd(u, v)$，则 $\mathrm{lcm}(u, v) = \frac{u \times v}{d}$
3. 在枚举因子 $d$ 时，$u$ 和 $v$ 都是 $d$ 的倍数，且都在区间内
4. 因此边 $(u, v)$ 会被生成

复杂度分析

时间复杂度

• 候选边数量：对于每个因子 $i$，生成 $O(\frac{R-L}{i})$ 条边
• 总边数：$\sum_{i=1}^{R} \frac{R-L}{i} = O((R-L) \log R)$
• 排序复杂度：$O((R-L) \log R \cdot \log((R-L) \log R))$
• 并查集复杂度：$O((R-L) \log R \cdot \alpha(R))$

总复杂度：$O((R-L) \log^2 R)$，在数据范围内可接受。

空间复杂度

• 边存储：$O((R-L) \log R)$
• 并查集：$O(R)$

代码实现细节

数据结构设计

struct UnionFind {
    vector<int> d;
    UnionFind(int n = 0): d(n, -1) {}
    int find(int x) {
        if (d[x] < 0) return x;
        return d[x] = find(d[x]);
    }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (d[x] > d[y]) swap(x, y);
        d[x] += d[y]; d[y] = x;
        return true;
    }
};

主算法流程

int main() {
    int l, r;
    cin >> l >> r;
    
    vector<tuple<ll, int, int>> es;
    
    // 生成候选边
    for (int i = 1; i <= r; ++i) {
        int nl = (l + i - 1) / i, nr = r / i;
        ll x = nl * i;
        
        for (int j = nl + 1; j <= nr; ++j) {
            ll y = (ll)j * i;
            es.emplace_back(lcm(x, y), x, y);
        }
    }
    
    // Kruskal算法
    ranges::sort(es);
    ll ans = 0;
    UnionFind uf(r + 1);
    
    for (auto [w, u, v] : es) {
        if (uf.unite(u, v))
            ans += w;
    }
    
    cout << ans << '\n';
    return 0;
}

样例解析

样例1：L=3, R=12

候选边生成过程：

• 因子1：连接所有相邻整数
• 因子2：连接4,6,8,10,12中的倍数关系
• 因子3：连接3,6,9,12中的倍数关系
• ...

最小生成树边： $(3,4), (3,5), (3,6), (3,7), (4,8), (3,9), (5,10), (3,11), (3,12)$

总边权：126

总结

算法亮点

1. 利用数论性质：通过枚举因子减少候选边数量
2. 高效的边生成：$O((R-L) \log R)$ 条候选边
3. 标准MST算法：使用Kruskal算法保证正确性

优化空间

• 可以进一步优化只连接相邻倍数，减少边数
• 使用更高效的gcd/lcm计算
• 对重复边进行去重

该解法充分利用了题目数据范围的特点，通过数学优化将问题规模控制在可处理范围内，是一个典型的数论与图论结合的优秀解法。