发布于2020年2月6日2020年2月6日算法竞赛中一类有关最大公因数 gcd 的求和问题 本文原载于 Math | UESTC_Jungle 如果遇到这样一类求和 T=∑A⊆S(a1,a2,…,an,k1,k2,…,km)⋅f(A)T = \sum_{A \subseteq S}{(a_1, a_2, \dots, a_n, k_1, k_2, \dots, k_m) \cdot f(A)}T=A⊆S∑(a1,a2,…,an,k1,k2,…,km)⋅f(A) 其中 aia_iai 是集合 AAA 里的元素,kjk_jkj 是额外需要求 gcd 的元素. 记 K=k1k2⋯kmK = k_1k_2\cdots{}k_mK=k1k2⋯km. 可以枚举 gcd,转换为 T=∑d∣K(d⋅∑A⊆S[d=(a1,a2,…,an,k1,k2,…,km)]⋅f(A))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)}T=d∣K∑(d⋅A⊆S∑[d=(a1,a2,…,an,k1,k2,…,km)]⋅f(A)) 继续阅读“算法竞赛中一类有关最大公因数 gcd 的求和问题”