HDU-6889 Graph Theory Class 题解

题目大意

给你一个n个顶点的无向图，求他的最小生成树的所有边的权值之和，第i点和第j点的边权值为$lcm(i+1,j+1)$。

解题思路

其实这个题目思路倒是挺简单的。

如果是合数的话，他的最小边肯定是他本身，并且是连接到他的因子。

如果是质数的话，最小值肯定是$lcm(i+1,2)$。

所以答案是3到n+1的和加上2~n+1的所有质数和减去2.

关键是这个n是1e10，怎么求这个质数和。。

后面组内大佬说可以用Min_25筛（听都没听过好吧。。

看了一小时，模板都没看懂。

后面直接套的别人大佬的模板了。。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <cstring>
#include <string>
#include <cmath>
#include <stack>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

ll qpow(ll a, ll b, ll k) {
    ll ans = 1;
    while (b) {
        if (b & 1)    ans = (ans * a) % k;
        a = (a * a) % k, b >>= 1;
    }
    return ans;
}

const int N = 200005;

namespace _Min25 {

    int p[N], name1[N], name2[N], flag[N], cnt, m;
    ll G[N], sum[N], a[N], t, n;

    inline void ini() {
        m = n = cnt = 0;
        for (int i = 0; i < N; i++) {
             name1[i] = name2[i] = flag[i] = G[i]  = a[i] = 0;
        }
    }

    inline int ID(ll x) {
        return x <= t ? name1[x] : name2[n / x];
    }

    inline ll calc(ll x) {
        return x * (x + 1) / 2 - 1;
    }

    inline ll f(ll x) {
        return x;
    }

    inline void init() {
        t = sqrt(n + 0.5);
        for (int i = 2; i <= t; i++) {
            if (!flag[i]) p[++cnt] = i, sum[cnt] = sum[cnt - 1] + i;
            for (int j = 1; j <= cnt && i * p[j] <= t; j++) {
                flag[i * p[j]] = 1;
                if (i % p[j] == 0) break;
            }
        }
        for (ll l = 1; l <= n; l = n / (n / l) + 1) {
            a[++m] = n / l;
            if (a[m] <= t) name1[a[m]] = m; else name2[n / a[m]] = m;
            G[m] = calc(a[m]);
        }
        for (int i = 1; i <= cnt; i++)
            for (int j = 1; j <= m && (ll)p[i] * p[i] <= a[j]; j++)
                G[j] = G[j] - (ll)p[i] * (G[ID(a[j] / p[i])] - sum[i - 1]);
    }

    inline ll solve(ll x) {
        if (x <= 1) return x;
        return ini(), n = x, init(), G[ID(n)];
    }

}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while (t--) {
        ll num, k; cin >> num >> k;
        ll fiv = qpow(2, k - 2, k);
        ll ans = ((num + 4) % k * (num - 1) % k * fiv) % k;
        ll tmp = _Min25::solve(num + 1);
        ans = (ans + tmp % k) % k;
        ans -= 2;
        cout << ans % k << endl;
    }
    return 0;
}