子序列和与GCD [英] Subsequence sum and GCD

问题描述

大约一个月前，我在一次编程挑战中遇到了这个问题，但社论尚未发布，因此我在这里提出。

I came across this question on a programming challenge about a month ago, but the editorial wasn't released so I am asking it here.

有一个大小为N的数组A。求和* K个长度为A的子序列的GCD。

There is an Array A of size N. Find the sum * GCD of K length subsequences of A.

示例：

如果A = [1、2、3]且K = 2，

If A = [1, 2, 3] and K = 2,

{1，2} = 3（总和）* 1（GCD）= 3

{1, 2} = 3(sum) * 1(GCD) = 3

{1，3} = 4（总和）* 1（ GCD）= 4

{1, 3} = 4(sum) * 1(GCD) = 4

{2，3} = 5（总和）* 1（GCD）= 5

{2, 3} = 5(sum) * 1(GCD) = 5

Ans => 3 + 4 + 5 = 12

Ans => 3 + 4 + 5 = 12

推荐答案

这是从头开始的（虽然没有彻底测试）：

Here it is from scratch (didn't test it thoroughly though):

让 C [k，i，d] 是所有 k 个长度为的子序列的数目A [1..i] ，这样他们的GCD等于 d 。

Let C[k, i, d] be the number of all k-length subsequences of A[1..i] such that GCD for them is equal to d.

然后

C[k, i, d] = Sum(C[k - 1, i - 1, d']) + C[k, i - 1, d]

其中对所有 d'求和，使得 gcd（A [i]，d’）= d 。

where summation is over all d' such that gcd(A[i], d') = d.

第一项（和）对应于我们从 A [1..i-1]中取所有序列的情况。 code>并在它们上附加 A [i] 。上一项-当我们不包括 A [i] 时。

The first term (the sum) corresponds to the case when we take all the sequences from A[1..i-1] and attach A[i] to them. The last term - when we don't include the A[i].

让 S [k，i，d] 是 A [1]的所有 k 个长度的子序列的总和。 .i] ，这样他们的GCD等于 d 。

Let S[k, i, d] be the total sum of all k-length subsequences of A[1..i] such that GCD for them is equal to 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 个值，我们可以计算出所需的值。

Then having S[k, i, d] and knowing all possible d values we can calculate the required value.

这篇关于子序列和与GCD的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！