首页 > 代码库 > 最小公倍数生成树
最小公倍数生成树
题意：
给出n，m，表示又m - n + 1个点的编号从n开始到m结束，两个点之间的权值为编号的最小公倍数，然后求最小生成树。
题解：
因为两个数最小公倍数在最小的情况下，是等于这两个数中较大的那一个数。所以可以贪心地对于一个节点a，连上它的倍数。
有一些情况：
①n = 4 m = 10的时候，因为最后会剩下一个9没有数和它相连，最好的情况下是与6连，从小到大枚举9的因数然后在乘以一个更小的因数使得在n~m的范围。
②n = 2 m = 10的时候，2连向了它所有的倍数，3要连向与2相连的6，最后会剩下以2,5,7为根的子树，现在需要合并子树因为都是素数不是第一种情况的合数，那么就直接合并好了。
代码：
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 1e6 + 7;
int n, m, prime[N], cnt;
bool isprime[N], vis[N];
LL ans;
void ListofPrime ()
{
for (int i = 2; i <= 1000000; ++i) isprime[i] = true;
for (int i = 2; i <= 1000000; ++i)
{
if (!isprime[i]) continue;
prime[++cnt] = i;
for (int j = 2 * i; j <= 1000000; j += i) isprime[j] = false;
}
}
int main ()
{
scanf ("%d%d", &n, &m);
if (n == m) {
puts("0");
return 0;
}
if (n == 1) {
printf ("%lld\n", (LL)(1 + m) * m / 2 - 1);
return 0;
}
ListofPrime();
for (int i = n; i <= m; ++i)
{
if (vis[i]) continue;
int flag = 0;
for (int j = 2 * i; j <= m; j += i)
{
if (!vis[i] || !vis[j])
{
if (vis[j]) flag = 1;
vis[i] = vis[j] = true;
ans = ans + j;
}
}
if (vis[i] && i != n && !flag) ans = ans + i * n;
}
for (int i = n; i <= m; ++i)
{
if (vis[i]) continue;
if (isprime[i]) ans = ans + i * n;
else
{
for (int j = 2; j <= cnt; ++j)
{
if (i % prime[j] != 0) continue;
for (int k = 1; k < j; ++k)
{
int xi = i / prime[j] * prime[k];
if (xi >= n && xi <= m)
{
ans = ans + i * prime[k];
break;
}
}
break;
}
}
}
cout << ans << endl;
return 0;
}
总结：
写代码之前需要先考虑好所有的情况，不然就会陷入debug的无限死循环QAQ
最小公倍数生成树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。