HDU6954 Minimum spanning tree（线性筛/贪心）

题目链接：HDU6954

题目描述：

给定 $n-1$​​ 个点，编号从 $2$​ 到 $n$，边的权值是两个点的最小公倍数。求最小的生成树总权值。

输入格式为，第一行输入测试样例组数 $T$。对于每组测试样例，输入一个整数 $n$。其中，$2\le n\le 10^7$。​

题目解析：

贪心，每条边权重最小，从而使得生成树的权值最小。显然，合数与它的质因子相连时，权值为该合数的值，对于质数，我们只要与最小的质数 2 相连即可。用线性筛筛出质数，然后用前缀和维护即可。

参考代码：

#include <iostream>

using namespace std;

typedef long long ll;

const int maxn = 1e7+10;

int n;
int vis[maxn];
ll prime[maxn], pre[maxn], sum[maxn];

void prework() {
   
    
    int cnt = 0;
    for (int i = 2; i <= 1e7; i++) {
   
        if (vis[i] == 0) {
   
            vis[i] = i;
            prime[cnt++] = i;
        }
        sum[i] = sum[i-1] + i;
        
        for (int j = 0; j < cnt; j++) {
   
            if (prime[j] > vis[i] || prime[j] > 1e7/i) {
   
                break;
            }
            vis[i*prime[j]] = prime[j];
        }
    }
    
    int cur = -1;
    
    for (int i = 2; i < maxn; i++) {
   
        if (prime[cur] < i) {
   
            cur++;
        }
        pre[i] = pre[i-1];
        if (prime[cur] == i) pre[i] += prime[cur];
    }
}

int main()
{
   
    prework();  
    int t;
    cin >> t;
    while (t--) {
   
        cin >> n;
        cout << (pre[n]-2) * 2 + (sum[n] - pre[n]) << endl;
    }
     return 0;
}