代码源每日一题div1 贪心线性筛最小生成数

柔情只为你懂 2024-03-31 12:49 70阅读 0赞

[最小生成数 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge]

题意：

![471a3025205c4f93a186b433ea79779f.png][]

思路：

标题最小生成数只是一个幌子，其实这就是一个贪心题

对于一个数x，去选另一个数y，使得 lcm(x,y) 最小

关于lcm，有一些性质：

1.质数 x 与任意数 k 的lcm为 x\*k

2.不是质数的 x和其约数 k 的lcm是x本身

因此，对于一个数，如果它是质数，它和任意数的lcm都是乘积，因此选最小，和2连边即可，贡献是2\*x

如果它不是质数，那么它和它的某个约数连边即可， 贡献是x本身

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=1e7+10;
    #define int long long
    int len=0,n;
    int prime[mxn],vis[mxn],dp[mxn];
    void init(int n){
        for(int i=2;i<=n;i++){
            if(!vis[i]) prime[++len]=i;
            for(int j=1;i*prime[j]<=n;j++){
                vis[i*prime[j]]=1;
                if(i%prime[j]==0) break;
            }
        }
    }
    void solve(){
        cin>>n;
        cout<<dp[n]<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        init(1e7);
        for(int i=3;i<=1e7;i++){
            if(!vis[i]) dp[i]=dp[i-1]+2*i;
            else dp[i]=dp[i-1]+i;
        }
        int T=1;
        cin>>T;
        while(T--)solve();
        return 0;
    }

**总结：**

**lcm的一些性质：**

**1.质数 x 与任意数 k 的lcm为 x\*k**

**2.不是质数的 x和其约数 k 的lcm是x本身**

[- _ - Daimayuan Online Judge]: http://oj.daimayuan.top/course/10/problem/811
[471a3025205c4f93a186b433ea79779f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/8523764a115749998ec04c9bdbf94764.png