本文原载于 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)}
则gcd为 d 的集合的贡献为
\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