自动搬运

查看原文

来自洛谷，原作者为

	fuqingchen **

搬运于2025-08-24 22:48:50，当前版本为作者最后更新于2023-07-30 19:58:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题链接

P9488 ZHY 的生成树

题目简述

ZHY 有一个 $n$ 个点的完全图，点 $u$ 与点 $v$ 的距离为 $\gcd(u,v)$，求这个完全图的最大生成树的边权之和。

解题思路

$30 pts$

直接暴力建图，跑一遍 $kruskal$。 不会 $kruskal$ 的点这里。

$60 pts$

这时候你离正解已经很近啦！

首先考虑 $n \le 10^6$。$n^2$ 建图纯属浪费（因为只有 $n-1$ 条边是有用的），我们可以先枚举这条边的边权，然后由 $i$ 向 $i$ 的倍数进行连边，就可以拿到 $60 pts$ 了。

$100 pts$

在 $60 pts$ 上优化，主要的重复在于枚举倍数时重复了。为了尽量减少这种情况，在枚举时可以只枚举倍数为质数的情况，稍微卡一卡就能过了。

参考代码

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

const int N = 1e7 + 10;
int n, m, fa[N], tot;
int prime[6000100], q, x, k;
bool isp[N];
void Prime() {
	for (register int i = 2; i <= 10000000; ++i) {
		if (isp[i] == 0) prime[++k] = i;
		for (register int j = 1; j <= k && i * prime[j] <= 10000000; ++j) {
			isp[i * prime[j]] = 1;
			if (!(i % prime[j])) break;
		}
	}
}
int find(int x) {
	if(x == fa[x]) return x;
	else return fa[x] = find(fa[x]);
}
void kruskal() {
	int cnt = 0;
	long long sum = 0;
	for(register int i = n / 2; i >= 1; --i) {
		int len = n / i;
		for (int u = 1; prime[u] * i <= n; ++u) {
			int x = find(i), y = find(prime[u] * i);
			++tot;
			if (x != y) {
				++cnt;
				sum += i;
				fa[y] = x;
				if (cnt == n - 1) {
					cout << sum;
					return;
				}
			}
		}
	}
}
signed main() {
	cin >> n;
	Prime();
	for (int i = 1; i <= n; ++i) fa[i] = i;
	kruskal();
	return 0;
}