贡献法+容斥原理，abc248G - GCD cost on the tree
目录
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
https://atcoder.jp/contests/abc248/tasks/abc248_g
二、解题报告
1、思路分析
考虑 f(x) 为 gcd 恰为 x 的路径长度和，g(x) 为 gcd 为 x 的倍数的路径长度和
那么 f(x) = g(x) - Σ f(y)，y = 2x, 3x....
由于[1, 1E5] 中，每个数的约数个数最大为一百多，那么我们考虑对每个数做因子分解，保存所有因子被包含在A[i] 的下标i
那么我们枚举 gcd(path) 的倍数g，跑树形dp，计算由点权为 g 的倍数的点 构成的路径总数，这是经典的贡献法，对于一条边<u, v>，在所有路径出现次数是 (树的大小 - siz[v]) * siz[v]
因为题目路径长度定义为点权，所以对于每个 g 的倍数构成的子树，我们需要额外加上一个组合数
最终答案为 Σxf(x)
2、复杂度
时间复杂度： O(d(V) * n)，d(V) 为 [1, V] 最大约数个数，V = 1E5，空间复杂度：O(n + Vd(V))
3、代码详解
#include <bits/stdc++.h> namespace ranges = std::ranges; namespace views = std::views; using i64 = long long; constexpr int M = 1E5; constexpr int P = 998244353; int add(int x, int y) { x += y - P; x += (x >> 31) & P; return x; } int mul(int x, int y) { return 1LL * x * y % P; } std::vector<int> fac[M + 1], st[M + 1]; int f[M + 1]; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); for (int i = 1; i <= M; ++i) { for (int j = i; j <= M; j += i) { fac[j].push_back(i); } } int N; std::cin >> N; std::vector<int> A(N); for (int i = 0; i < N; ++i) { std::cin >> A[i]; for (int x : fac[A[i]]) { st[x].push_back(i); } } std::vector<std::vector<int>> adj(N); for (int i = 1; i < N; ++i) { int u, v; std::cin >> u >> v; --u; --v; adj[u].push_back(v); adj[v].push_back(u); } std::vector<bool> vis(N); std::vector<int> siz(N), val; auto dfs = [&](this auto &&self, int u, int g) -> void { siz[u] = 1; vis[u] = true; for (int v : adj[u]) { if (vis[v] || A[v] % g > 0) { continue; } self(v, g); siz[u] += siz[v]; val.push_back(siz[v]); } }; for (int g = 1; g <= M; ++g) { for (int i : st[g]) { vis[i] = false; } for (int i : st[g]) { if (!vis[i]) { val.clear(); dfs(i, g); for (int x : val) { f[g] = add(f[g], mul(siz[i] - x, x)); } f[g] = add(f[g], 1LL * siz[i] * (siz[i] - 1) / 2 % P); } } } int ans = 0; for (int g = M; g > 0; --g) { for (int x = g + g; x <= M; x += g) { f[g] = add(f[g], P - f[x]); } ans = add(ans, mul(f[g], g)); } std::cout << ans << '\n'; return 0; }