自动搬运

查看原文

来自洛谷，原作者为

	will7101 **

搬运于2025-08-24 21:52:43，当前版本为作者最后更新于2017-05-30 22:53:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一句话题意

求无向图的所有生成树的权值gcd之和。

20分做法

暴力枚举边的集合，判断是否是生成树，计算gcd并求和。

复杂度$O(N logW 2^M)$

30分做法

在20分做法的基础上加一些剪枝，或者用dfs来枚举生成树。

50分做法

因为值域不大，考虑枚举gcd的值并进行容斥（反演）。

推式子：

设$f(n)=$权值gcd为n的生成树个数，我们发现$f(n)$不是很好直接计算。

于是设$F(n)=$权值gcd被n整除的生成树个数，

显而易见，$F(n)=\sum_{n|d} f(d)$。

而且$F(n)$比较容易得到（可以通过矩阵树定理在$O(N^3)$的时间内计算）。

进行莫比乌斯反演，得到$f(n)=\sum_{n|d} \mu(\frac{d}{n})F(d)$

于是

$ans=\sum_{n=1}^W {n f(n)}$

$=\sum_{n=1}^W {n \sum_{n|d} {\mu(\frac{d}{n})F(d)}}$

$=\sum_{d=1}^W {F(d) \sum_{n|d} {n \mu(\frac{d}{n})}}$

$=\sum_{d=1}^W {F(d) \phi(d)}$

枚举d从1到W，然后加入d整除权值的边，使用矩阵树定理计算F，注意判断生成树个数为0的情况（图不联通）。

复杂度$O(W(M+N^3))$

另外20分做法（v=u+1）

注意到生成树都是一条链，不需要使用矩阵树定理，直接利用乘法原理计算。

复杂度$O(WM)$

100分做法

在50分做法的基础上进一步优化：

注意到很多时候生成数个数为0（图不联通），一个显然的充分条件是满足条件的边数<N-1，所以我们可以预先筛掉这些情况。

对于每一条边，只会对它权值的因数d造成影响，然后统计每个数作为因数出现了多少次，小于N-1的不用计算。

对于小于$\sqrt{W}$的因子，它们每个最多出现一次；对于超过$\sqrt{W}$的因子，由于边权不超过$W$，每个边权至多只有一个大因子。所以有效的因子总数最多为$\sqrt{W}+\frac{M}{N-1}$，约为2000。

复杂度$O((\sqrt{W}+\frac{M}{N-1})(M+N^3))$。