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

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

最小生成数 - 题目 - 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:

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int mxn=1e7+10;
  4. #define int long long
  5. int len=0,n;
  6. int prime[mxn],vis[mxn],dp[mxn];
  7. void init(int n){
  8. for(int i=2;i<=n;i++){
  9. if(!vis[i]) prime[++len]=i;
  10. for(int j=1;i*prime[j]<=n;j++){
  11. vis[i*prime[j]]=1;
  12. if(i%prime[j]==0) break;
  13. }
  14. }
  15. }
  16. void solve(){
  17. cin>>n;
  18. cout<<dp[n]<<'\n';
  19. }
  20. signed main(){
  21. ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  22. init(1e7);
  23. for(int i=3;i<=1e7;i++){
  24. if(!vis[i]) dp[i]=dp[i-1]+2*i;
  25. else dp[i]=dp[i-1]+i;
  26. }
  27. int T=1;
  28. cin>>T;
  29. while(T--)solve();
  30. return 0;
  31. }

总结:

lcm的一些性质:

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

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

发表评论

表情:
评论列表 (有 0 条评论,65人围观)

还没有评论,来说两句吧...

相关阅读