题解：P15367 秋季限定生成树问题

瞎写写过了，有点诡异了。

使用 Boruvka 刻画完全图最大生成树，考虑给每个点 \(u\) 找到最优的 \(v\) 使得 \(\operatorname{lcm}(u,v)+\gcd(u,v)\) 最大。把边权化成 \(\dfrac{uv}{\gcd(u,v)}+\gcd(u,v)\)，直觉上让 \(\gcd(u,v)\) 取 \(1\) 会更优。此时设

\[f(u)=\max\limits_{\substack{u<i\leq n\\\gcd(u,v)=1}}i \]

那么取 \(v=f(u)\) 是最优的。

证明

放缩一下，当 \(\gcd(u,v)\geq 2\) 时，显然 \(\dfrac{uv}{\gcd(u,v)}+\gcd(u,v)\leq \dfrac{un}2+u\)，那么我们证明 \(uf(u)+1\geq \dfrac{un}2+u\) 即可。

这里引出伯特兰-切比雪夫定理：

对于任意正整数 \(n\geq 2\)，\((n,2n)\) 内至少存在一个质数。

因此 \(f(u)>\dfrac n2\)。结论得证。\(\Box\)

对于每个点 \(1\leq u<n\) 连一条 \((u,f(u))\) 的边，这样得到的恰好是树结构，因此这样连出来的就是我们要的最大生成树。

问题转化为求 \(\sum\limits_{i=1}^{n-1}(if(i)+1)\)。由于 \(f(i)\) 和 \(n\) 之间的距离很小，考虑设 \(f(i)=n-g(i)\)，这样我们求出 \(\sum\limits_{i=1}^{n-1}ig(i)\) 即可。套路地转化为求

\[\sum_{v=0}^{\infty}\sum_{i=1}^{n-1}[g(i)>v]i \]

考虑到

\[g(i)>v\Leftrightarrow \forall n-v\leq x\leq n,\gcd(x,i)>1 \]

可以莫反转化为

\[\begin{align*} &\prod_{x=n-v}^n[\gcd(x,i)>1]\\ =&\prod_{x=n-v}^n\left(1-\sum_{d\mid x}[d\mid i]\mu(d)\right)\\ =&\prod_{x=n-v}^n\sum_{\substack{d\mid x\\ d>1}}-[d\mid i]\mu(d) \end{align*} \]

\(v\) 很小，考虑直接 DFS。我们只用考虑 \(\mu(d)\neq 0\) 的 \(d\)，也就是 \(d\) 应当能表示成若干不同质数之积。于是每次从大到小加入一个 \(x\) 时，我们用 Pollard-Rho 求出 \(x\) 的质因子集合 \(P(x)\)，枚举 \(P(x)\) 的真子集作为当前层的 \(d\)。DFS 过程中再维护一下每一层的 \(d\) 的 \(\operatorname{lcm}\)，和每一层 \(-\mu(d)\) 的乘积，然后每一层对答案的贡献就是 \(<n\) 的数中 \(\operatorname{lcm}\) 的倍数个数。

其实可以实现得更简单。观察到如果前面层的 \(\operatorname{lcm}\) 和当前层的 \(x\) 不是互质的，那么 \(\gcd(x,i)>1\) 必然成立，此时我们不必枚举子集，可以直接递归到下一层解决。那么加上这个剪枝之后，每个有效层的 \(d\) 都是互质的，于是维护 \(\operatorname{lcm}\) 就自然地变成了维护乘积。过程中需要保证乘积是 \(<n\) 的。

时间复杂度不太会算。可以简单分析一下效率，考察 Jacobsthal 函数 \(J(n)\)：

\(J(n)\) 是最小的 gap 使得对于任意的正整数 \(i\)，\([i,i+J(n))\) 中至少存在一个正整数与 \(n\) 互质。

那么显然 \(v\leq \max\limits_{i=1}^nJ(i)\)。由 \(\omega(n)\leq 15\)，直接查表 OEIS A048670 可以得到 \(v\leq L=100\)。因此质因数分解的部分时间复杂度是 \(\mathcal{O}(Ln^{1/4})\)。至于 DFS 状态数，可以得到一些 \(2^{\pi(L)}\) 的状物，但是显然不满，不是很会分析。

少用点除法就卡过去了，跑的挺快。

主要代码

inline void dfs(int x, ull d, int s) {if (x) {ull cnt = (n - 1) / d;ui sum = (u128)d * (cnt + 1) * cnt >> 1;ans += sum * s;}ull cur = n - x;if (cur == 1) return;if (tot < x + 1) fc[tot++] = Factorize(cur);bool ok = 0;for (ull p : fc[x]) if (d % p == 0) { ok = 1; break; }if (ok) return dfs(x + 1, d, s);int sz = fc[x].size();for (int S = 1; S < 1 << sz; ++S) {ull prod = 1;bool suc = 1;int pc = 0;for (int i = 0; i < sz; ++i) if (S >> i & 1) {if (n - 1 < (u128)fc[x][i] * d * prod) { suc = 0; break; }prod *= fc[x][i], ++pc;}if (suc) dfs(x + 1, d * prod, pc & 1 ? s : -s);}
}