Сумма подпоследовательности и GCD

Question

Я сталкивался с этим вопросом о проблеме программирования около месяца назад, но передовая статья не была выпущена, поэтому я задаю его здесь.

Существует массив A размера N. Найти сумму * GCD K-подпоследовательностей длины A.

Пример:

Если A = [1,2, 3] и K = 2,

{1, 2} = 3 (сумма) * 1 (GCD) = 3

{1, 3} = 4 (сумма) * 1(GCD) = 4

{2, 3} = 5 (сумма) * 1 (GCD) = 5

Ans => 3 + 4 + 5 = 12

Answer 1

Вот он с нуля (хотя и не проверял его полностью):

Пусть C[k, i, d] будет числом всех подпоследовательностей k длины A[1..i], так что 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] - общая сумма всех подпоследовательностей k длины A[1..i], так что 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, мы можем вычислить требуемое значение.