博客

题意：给定 n-1 个点，编号从 2 到 n，两点 a 和 b 之间的边权重为 lcm(a, b)。 请找出它们形成的最小生成树。 lcm(a, b) 是能被 a 和 b 整除的最小正整数。求即最小生成树边缘权重和。



题解：可以将所有数分为质数点和合数点，当一个数为质数点的时候，最小公倍数为两个数的乘积，为了使权重和最小，故另一个数为最小值2,。当该数为合数的时候，最小公倍数最小为当前的合数，所以最后的答案为素数*2+合数。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e7 + 5;
const int mod = 1e9 + 7;
int a[maxn], prime[maxn], isprime[maxn];
int num = 1;
void s() {
	for (int i = 2; i < maxn; i++) {
		if (!isprime[i]) prime[num++] = i;
		for (int j = 1; j <= num && i * prime[j] < maxn; j++)

		{
			isprime[prime[j]*i] = 1;
			isprime[prime[j]*i] = 1;
			if (i % prime[j] == 0) break;
		}

	}

}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	s();
	for (int i = 3; i <= maxn; i++) {
		if (isprime[i]) a[i] = a[i - 1] + i;
		else a[i] = a[i - 1] + 2 * i;
	}
	while (t--) {
		//TODO
		int n;
		cin >> n;

		cout << a[n] << endl;
	}

}