CF870F Paths
数论
题解
OI
题意
照搬洛谷翻译
给定一张个顶点的图, 对于点, 如果,则到有一条长度为1的无向边. 令表示从i到j的最短路, 如果无法到，则.
求节点两两之间距离之和.
分析
先考虑两个数之间的路径情况.
- : 直接连边
- : 设是的最小质因子
- : 可以走, 路径长度为
- : 不妨设, 那么有, 又有, 故一定是质数, 可以考虑存在一条这样的路径: , 路径长度为, 并且当时, 不存在这样的路径.
若以作为跳板来转移已经无解了, 用比更大的数来转移也不会有解, 因此路径只有以上三种情况.
然后考虑如何统计答案, 应该考虑分种类统计条数.
- : 利用欧拉函数来线性统计.
- : 不好直接做, 用总情况数来减.
- : 还是令, 若这样的路径存在, 需满足以下条件: 根据上面的推理, 是质数, 所以只需统计最小质因子是的数的个数(线性筛可以做到), 对于的就是长度为的路径, 否则就是不连通.
代码
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
| #include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <iostream>
using namespace std;
typedef long long int64;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e7 + 10;
bool isnt_prime[MAXN];
int64 prime[MAXN], phi[MAXN];
int64 mfac_cnt[MAXN], mfac_sum[MAXN];
#define sum(l, r) (((r) < (l)) ? 0 : (mfac_sum[(r)] - mfac_sum[(l) - 1]))
int main() {
int64 n;
cin >> n;
isnt_prime[1] = true;
phi[1] = 1;
int prime_cnt = 0;
for (int i = 2; i <= n; i++) {
if (!isnt_prime[i]) {
prime[prime_cnt++] = i;
mfac_cnt[i]++;
phi[i] = i - 1;
}
for (int j = 0; j < prime_cnt; j++) {
if (i * prime[j] > n) break;
isnt_prime[i * prime[j]] = true;
mfac_cnt[prime[j]]++;
if (i % prime[j] == 0) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
} else {
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
}
for (int i = 1; i <= n; i++) {
mfac_sum[i] = mfac_sum[i - 1] + mfac_cnt[i];
}
int64 path2 = 0;
for (int i = 1; i <= n; i++) {
path2 += phi[i] - 1;
}
int64 path1 = (n - 1) * (n - 2) / 2 - path2;
int64 ans = path2 * 2 + path1;
for (int i = 0; i < prime_cnt; i++) {
ans += mfac_cnt[prime[i]] *
sum(max(prime[i] + 1, n / prime[i] + 1), max(prime[i], n / 2));
ans -= 2 * mfac_cnt[prime[i]] * sum(max(prime[i], n / 2) + 1, n);
}
cout << ans << endl;
return 0;
}
|
