公倍树

题目描述

某图上有 $n$ 个点分别标号为 $2,3…n + 1$

任意两点之间有一条边，边长为两条标号边的最小公倍数。

求该图最小生成树的边长总和模 $998244353$。

输入格式

一个整数 $n$

输出格式

一个整数，为该图最小生成树的边长总和模$998244353$

样例 #1

样例输入 #1

3

样例输出 #1

10

样例 #2

样例输入 #2

10

样例输出 #2

89

提示

在第一个样例中，图上只有 $2,3,4$ 号点，最小生成树中 $2$ 号和 $3,4$ 号分别连一条边，权值分别为 $lcm(2,3)=6$ 和 $lcm(2,4)=4$。

数据范围：

保证对于前 $30\%$ 的数据，$n \le 10$

保证对于前 $50\%$ 的数据, $n \le 10^5$

保证对于 $100\%$ 的数据, $1 < n \le 10^7$

开始写个最小生成树暴力, 可拿30tps

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// 数组大小只要超过30%的范围就行了不用开太大
const ll N = 1e5 + 10, mod = 998244353;
int h[N], e[N], ne[N], idx;
int p[N];

struct Kruskal
{
    ll a, b, w;

    bool operator< (const Kruskal v) const
    {
        return w < v.w;
    }
} g[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);

    return p[x];
}

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}

ll lcm(ll a, ll b)
{
    return a / gcd(a, b) * b;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    int m = 0;
    for (int i = 2; i <= n + 1; i++)
        for (int j = 2; j <= n + 1; j++)
            if (i != j)
                g[m++] = {i, j, lcm(i, j)}; // 直接暴力建边

    sort(g, g + m);

    for (int i = 1; i <= n; i++) p[i] = i;

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i++)
    {
        ll a = g[i].a, b = g[i].b, w = g[i].w;

        a = find(a), b = find(b);

        if (a != b)
        {
            p[a] = b;
            res = (res + w) % mod;
            cnt++;
        }
    }

    cout << res;


    return 0;
}

我们发现直接暴力建边会有很多不必要的边, 最后只需要n-1条.

可以发现枚举每个合数和当前合数的质数倍, 和所有质数(2是最小的)

进行建边即可拿到60tps, 运用线性筛可卡空间至90tps

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll N = 1e7 + 10, M = 664580, mod = 998244353;
int p[N];
int primes[M];
bool st[N];
int m, k;

// 此时空间已在边界
struct Kruskal
{
    int a, b;
    ll w;

    bool operator< (const Kruskal v) const
    {
        return w < v.w;
    }
} g[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);

    return p[x];
}

ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}

ll lcm(ll a, ll b)
{
    return a / gcd(a, b) * b;
}

void get_primes(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i]) primes[m++] = i;

        for (int j = 0; j < m && i * primes[j] <= n; j++)
        {
            st[i * primes[j]] = true;

            g[k++] = {i, i * primes[j], i * primes[j]};

            if (i % primes[j] == 0) break;
        }
    }
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    get_primes(n + 1);

    for (int i = 0; i < m; i++) g[k++] = {2, primes[i], lcm(2, primes[i])}; // 让和所有质数建边

    sort(g, g + k);

    for (int i = 1; i <= n; i++) p[i] = i;

    ll res = 0;
    int cnt = 0;
    for (int i = 0; i < k; i++)
    {
        int a = g[i].a, b = g[i].b;
        ll w = g[i].w;

        a = find(a), b = find(b);

        if (a != b)
        {
            p[a] = b;
            res = (res + w) % mod;
            cnt++;
        }
    }

    cout << res;


    return 0;
}

100tps, 我们可以发现2与所有质数的建边一定是在最小生成树以内的

因为2与所有质数(不包括2本身)的连边的权值严格最小.

但这些边的数量是远远不及n-1的, 贪心的去想我们希望加上剩下的合数权值, 没有任何多余部分, 这是否可行呢?

可行, 每个合数一定能被质因数分解, 所以任然满足刚才60tps思想中的i连向i * primes[j]的建边

所以最终解法为先用初始化所有的质数

从3到n+1开始遍历, 若为质数res += 2 * i( $lcm(2, x) = 2 * x$ ), 否则res += i;

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll N = 1e7 + 10, M = 664580, mod = 998244353;
int primes[M], cnt;
bool st[N];

void get_primes(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i]) primes[cnt++] = i;

        for (int j = 0; j < cnt && i * primes[j] <= n; j++)
        {
            st[i * primes[j]] = true;

            if (i % primes[j] == 0) break;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    get_primes(n + 1);

    ll res = 0;
    for (int i = 3; i <= n + 1; i++)
        if (st[i]) res = (res + i) % mod;
        else res = (res + 2 * i) % mod;

    cout << res;


    return 0;
}
/*
lcm(primes[i], 2)
i * primes[i]
1 2 3 4
*/