2021 杭电多校1 - vjudge

Minimum spanning tree

题目链接

题目大意：

有n-1个点（2~n），两两间的权值为lcm(a, b)，问最小生成树的权值和为多少？

解题思路：

经过演算得出，最小生成树的情况是所有的值都与2相连，得到的权值和最小，因此素数应该乘2，合数不变，然后求和

ACCode:

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

const int N = 1e7 + 10;
const int M = 1e9 + 10;

// const int N=1e7+1;
int prime[N], cnt = 0;
//prime存储的是素数表
bool vis[N];
//如果vis[n]的值为true，则该数为素数
//使用bool型，节省空间；
void get_prime()
{
    memset(vis, true, sizeof(vis));
    vis[0] = vis[1] = 0;
    for (int i = 2; i < N; i++)
    {
        if (vis[i])
        {
            prime[++cnt] = i;
            for (int j = 2; j * i < N; j++)
                vis[i * j] = false;
        }
    }
}

long long ans[N];
int main()
{
    // freopen("input.in", "r", stdin);
    // freopen("output.out","w", stdout);
    get_prime();
    long long curNum = 0;
    for (int i = 3; i < N; i++)
    {
        if (vis[i])
            curNum += (2 * i);
        else
            curNum += i;
        ans[i] = curNum;
    }
    // cout << ans[6] << endl;

    int n, x;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> x;
        cout << ans[x] << endl;
    }
    return 0;
}