最小生成数 - 题目 - 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
- 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<
'\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本身