NFLS 2024.9.13 T4

题意

给出一棵以 \(1\) 为根的树 \((n\le 10^4)\) 和 \(k(k\le 10^{14})\)。

要求给每个点一个 \(a_i\) 使得 \(a_i\mid a_{fa_i}\)，且 \(\prod a_i\le k\)。

思路

这题有一个很妙的思路，但不是前面。

设最终的 \(\prod a_i = S\)，可以对 \(S\) 的每个质因子单独考虑。

设 \(g(s)\) 为给每个点一个 \(a_i\) 使得 \(\sum a_i = s\) 且 \(a_i \le a_{fa_i}\) 的方案。可以简单 \(O(n\log^4 k)\)，前缀和加剪枝做到极小（应该）常数 \(O(n\log^3 k)\)。

将 \(S\) 唯一分解 \(= \prod p_i^{q_i}\)，有 \(f(S) = \prod g(q_i)\)，而 \(g(1) = 1\) 故 \(f(S) = \prod\limits_{q_i > 1}g(q_i)\)。

令 \(T = \prod\limits_{q_i > 1}p_i^{q_i}\)，有 \(a^2b^3\) 与 \(T\) 为双射（应该）（powerful number 筛），那么 \(T\) 的数量为 \(O(\sqrt k)\)，可以直接 dfs 得到。

但是，我们发现这并不好算，因为 \(p_i\) 之间要求不重复，所以在求每个 \(T\) 对应多少 \(S\) 时非常麻烦。（会算重）

想到算重主要是 \(q_1 > all q_i(i > 1)\) 导致的，如果我们先令 \(a_1 = \operatorname{lcm} a_i(i > 1), T = \prod a_i\)，那么最终的方案就是 \(\frac{S}{T}\)，因为所有 \(q_1\) 都由某个代表元计数了。