代码源每日一题div1 贪心 线性筛 最小生成数
最小生成数 - 题目 - Daimayuan Online Judge
题意:
思路:
标题最小生成数只是一个幌子,其实这就是一个贪心题
对于一个数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本身
还没有评论,来说两句吧...