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; }
|