洛谷 P8207 分析（别看）

科技起源的小号1

2026-09-07 21:13:17

发布于：天津

3阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最小值

1.2 题目背景、允许、禁止与限制

背景：

允许：

1.3 题目数据范围与猜测

$1 \le L \le R \le 10^6 \longrightarrow O(n)\rightarrow$ 显然建边是不可取的

1.4 一句话概括题意

现在有 $L,L+1,\cdots,R-1,R$ 的若干节点组成的无向完全图
节点 $u$ 和 $v$ 之间的边权为 $lcm(u,v)$
求这个张图的最小生成树

2 题目破题推导

2.1 第一步：数学

因为我们知道如果 $gcd(u,v) \ne 1$ ，则 $lcm(u,v)$ 一定 $<$ 当 $gcd(u,v)=1$ 的时候
因此对于每个数 $w$ ，找到区间内第一个 $w$ 的倍数 $boss$ ，然后只把 $boss$ 和后面所有 $w$ 的倍数相连
对于这些边（边的数量约为 $O(R~log~R)$ ）再进行MST即可
那么现在只需要确保整张图连通即可：既然 $w$ 从 $1$ 开始，代表整张图第一轮一定就连通了，剩下只有可能是补充“可能”更优的候选边
边数一定严格 $\le R~ln~R$

3 模型匹配

MST+LCM

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;
#define int long long

int l, r;
struct edge{
    int from, to;
    int w;
};
vector<edge> e;
bool cmp(edge x, edge y){
    return x.w < y.w;
}
int lcm(int x, int y){
    return (x * y) / __gcd(x, y);
}
const int N = 1e6 + 10;
int fa[N];
void init(){
    for (int i = 1;i <= r;i++){
        fa[i] = i;
    }
}
int get(int x){
    if (fa[x] != x){
        fa[x] = get(fa[x]);
    }
    return fa[x];
}

signed main(){

    cin >> l >> r;
    for (int w = 1;w <= r;w++){
        int boss = -1;
        for (int i = w;i <= r;i += w){
            if (l <= i){
                boss = i;
                break;
            }
        }
        if (boss == -1 || boss > r) continue;
        for (int i = boss + w;i <= r;i += w){
            e.push_back({boss, i, lcm(boss, i)});
            e.push_back({i, boss, lcm(i, boss)});
        }
    }
    sort(e.begin(), e.end(), cmp);///////////
    init();
    int cnt = 0;
    int sum = 0;
    for (edge now : e){
        int u = now.from, v = now.to;
        u = get(u);
        v = get(v);
        if (u != v){
            fa[u] = v;
            cnt++;
            sum += now.w;
            if (cnt == r - l){
                break;
            }
        }
    }
    cout << sum;
    
    return 0;
}