算法题解贪心 HDOJ 2021“MINIEYE杯”中国大学生算法设计超级联赛素数筛

HDOJ6954 Mininum spanning tree【素数筛】

yngcy2021-07-242024-10-26

题目链接：HDU6954

题意

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

题解

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

参考代码

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