P9488 ZHY 的生成树

题目描述

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

输入格式

一个正整数 $n$。

输出格式

一个整数，表示这个最大生成树的边权之和。

输入输出样例 #1

输入 #1

4

输出 #1

4

输入输出样例 #2

输入 #2

30

输出 #2

183

输入输出样例 #3

输入 #3

100

输出 #3

1916

说明/提示

本题采用捆绑测试。

$\text{Subtask}$ $0$(10pts)：$n\le 5$。

$\text{Subtask}$ $1$(20pts)：$n\le 1000$。

$\text{Subtask}$ $2$(30pts)：$n\le 10^6$。

$\text{Subtask}$ $3$(40pts)：$n\le 10^7$。

对于所有测试数据，$1\le n\le 10^7$。

C++实现

#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;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容