C++莫比乌斯反演Mobius怎么化简树上数论函数-C++-PHP中文网

莫比乌斯反演本身不依赖树结构；所谓“树上数论函数”非标准概念，实指在树形dp或子树求和中嵌套μ(d)、∑_{d|n}等数论操作，其优化核心是将暴力枚举约数/倍数转为按值分组+dfs序差分+桶统计，并让μ(d)起符号开关作用而非状态维度，否则易致复杂度爆炸或结果错误。

c++莫比乌斯反演mobius怎么化简树上数论函数

莫比乌斯反演本身不依赖树结构，所谓“树上数论函数”不是标准概念——它通常指在树形 DP 或子树求和中嵌套了 μ(d)、∑_{d|n} 这类数论求和，而化简的关键不是改写反演公式，是把「枚举约数」或「枚举倍数」的暴力逻辑，换成可合并、可换根、可差分的树上操作。

常见错误是写成类似这样的伪代码：

for each node u:
  for d = 1 to max_val:
    for v in subtree(u) where val[v] % d == 0:
      f[u] += μ(d) * g[v]

这三重循环实际复杂度接近 O(n × max_val × log max_val)，且无法利用树的父子关系做预处理。问题本质不是反演错了，而是没把数论卷积（如 f = μ * g）和树上前缀/差分结构对齐。

真正可行的路径只有一条：把「对每个 d 枚举所有 d 的倍数节点」转为「对每个节点 v，只向其所有约数 d 对应的虚点 / 桶里贡献」——也就是反演前的预处理必须离线、按值分组、再挂到树上。

适用场景：统计满足 gcd(val[u], val[v]) == 1 的树上点对，或求 ∑_{u} ∑_{v ∈ subtree(u)} [gcd(val[u], val[v]) == 1] 这类式子。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

先离散化所有 val[i]，并预处理出每个数的所有约数（用试除或线性筛约数表），时间复杂度 O(V√V)，V 是值域大小
对每个值 v0，收集所有满足 val[u] == v0 的节点 u，记为 nodes_by_val[v0]
对每个约数 d，建一个桶 bucket[d]，遍历每个 v0，对每个 d | v0，把 nodes_by_val[v0] 中所有节点的 DFS 入/出时间戳区间加到 bucket[d] 上（用差分数组或线段树）
最后对每个 d，跑一遍 DFS，在进入/离开节点时累加/减去 bucket[d] 当前覆盖的节点数，乘上 μ(d) 即得反演后结果

很多实现失败是因为把 μ(d) 当作普通系数塞进 DP 状态，导致状态爆炸。正确做法是：让 μ(d) 控制「是否计入」，而不是「如何转移」。

例如定义 dp[u][d] 表示以 u 为根的子树中，满足 d | val[x] 的节点 x 的个数 —— 这个 d 是约数索引，不是状态维数。然后最终答案是 ∑_d μ(d) × dp[root][d]。

不要用 map 或 unordered_map 存 dp[u]，改用 vector indexed by d（d 范围必须提前压缩，比如只存 ≤ max_val 的有 μ≠0 的 d）
合并子树时，不是 dp[u][d] += dp[v][d]，而是对每个 d，只加一次；若同一 d 在多个子树中出现，仍只计数，不叠加符号
μ(d) == 0 的 d 完全跳过，这类 d 至少有一个平方因子，提前筛掉能省 60%+ 时间

当树退化成链、或值域远大于节点数（比如 n=1e5，max_val=1e7），常规分组法会内存炸穿。这时必须切换策略：

放弃「对每个 d 建桶」，改用「对每个节点 u，只枚举 val[u] 的约数 d，更新全局数组 cnt[d]++」，然后 DFS 过程中用栈维护从根到当前节点路径上的 cnt[d] 值 —— 这是真正的树上莫比乌斯，轻量但仅适用于路径相关问题
若需支持换根，不能用 DFS 序差分，得用 Euler Tour + Fenwick Tree，且 μ(d) 必须预先绑定到每个 d 对应的修改事件中，否则换根时符号错位
注意 μ(1) == 1，但很多手写筛漏掉这个特判，导致整个反演结果偏移

树和数论交汇处没有银弹，关键在识别哪部分该离线分组、哪部分该在线 DFS 维护、以及 μ(d) 到底是权重还是开关——这三个判断错了任意一个，复杂度就回不到 O(n log V)。