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筛(听都没听过好吧。。

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

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

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#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;
}
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信