分类： 算法

本文原载于 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)}$

继续阅读“算法竞赛中一类有关最大公因数 gcd 的求和问题”