大约一个月前，我在一次编程挑战中遇到了这个问题，但社论尚未发布，所以我在这里提出这个问题。
有一个大小为 N 的数组 A。求 A 的 K 个长度子序列的总和 * GCD。
示例:
If A = [1, 2, 3] and K = 2,
{1, 2} = 3(sum) * 1(GCD) = 3
{1, 3} = 4(sum) * 1(GCD) = 4
{2, 3} = 5(sum) * 1(GCD) = 5
Ans => 3 + 4 + 5 = 12
最佳答案
这是从头开始的(虽然没有彻底测试):
令 C[k, i, d] 为 A[1..i] 的所有 k 长度子序列的数量这样它们的 GCD 就等于 d。
然后
C[k, i, d] = Sum(C[k - 1, i - 1, d']) + C[k, i - 1, d]
其中对所有 d' 进行求和，使得 gcd(A[i], d') = d。
第一项(总和)对应于我们从 A[1..i-1] 中获取所有序列并附加 A[i] 的情况给他们。最后一项 - 当我们不包含 A[i] 时。
设 S[k, i, d] 为 A[1..i] 的所有 k 长度子序列的总和> 这样它们的 GCD 就等于 d。
然后
S[k, i, d] = Sum(C[k - 1, i - 1, d'] * A[i] + S[k - 1, i - 1, d']) + S[k, i - 1, d]
其中对所有 d' 求和，使得 gcd(A[i], d') = d。
然后有了 S[k, i, d] 并知道所有可能的 d 值，我们就可以计算所需的值。
关于algorithm - 序列和与 GCD，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52010836/