算法竞赛中一类有关最大公因数 gcd 的求和问题

本文原载于 Math | UESTC_Jungle

如果遇到这样一类求和

T = \sum_{A \subseteq S}{(a_1, a_2, \dots, a_n, k_1, k_2, \dots, k_m) \cdot f(A)}

其中 a_i 是集合 A 里的元素,k_j 是额外需要求 gcd 的元素. 记 K = k_1k_2\cdots{}k_m.

可以枚举 gcd,转换为

T = \sum_{d|K}{\left(d \cdot \sum_{A \subseteq S}{[d = (a_1,a_2,\dots,a_n, k_1, k_2, \dots, k_m)]\cdot{}f(A)}\right)}

一般 f(A) 仅与集合 A 的大小有关,即

f(A) = h(|A|)

则有

T = \sum_{d | K}{\left(d \cdot \sum_{l = 1}^{|S|}{h(l)\sum_{A\subseteq{S}\ \text{且}\ |A|=l}{[d = (a_1,a_2,\dots,a_n,k_1,k_2,\dots,k_m)]}}\right)}

遍历集合 S 的每个数的因子,统计出因子 d 的出现次数为 c_d
那么大小为 l、最大公因数至少为 d 的集合的个数为

g(d,l) = \binom{c_d}{l}

\phi(d) = \sum_{l = 1}^{\min{c_d,|S|}}{h(l)g(d,l)}

gcdd 的集合的贡献为

\Phi(d) = \phi(d) – \sum_{t | (K / d)}\Phi(t)

容斥一波就可以搞出来了

T = \sum_{d | K}{d \cdot \Phi(d)}


下面是一些常见的 h(l),一般 c_d \le |S|:
* h(l) = l, \phi(d) = \sum_{l=1}^{c_d}{l\binom{c_d}{l}} = c_d \cdot 2^{c_d-1} – 1
* h(l) = \lambda^{l}, \phi(d) = \sum_{l=1}^{c_d}{\lambda^l\binom{c_d}{l}} = (1 + \lambda)^{c_d} – 1

作者:
孑枵 Abreto版权所有,转载时必须以链接形式注明作者和原始出处及本声明,本站有权追究其法律责任。

发表评论

您的电子邮箱地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据