17. Числовые последовательности: #297043

Так как $26=2\cdot13$, произведение двух чисел должно содержать одновременно множители $2$ и $13$.

Разделим все числа последовательности на четыре группы:

• делятся на $26$;
• делятся на $2$, но не делятся на $13$;
• делятся на $13$, но не делятся на $2$;
• не делятся ни на $2$, ни на $13$.

В файле получаем:

• $397$ чисел, делящихся на $26$;
• $4620$ чисел, делящихся на $2$, но не на $13$;
• $387$ чисел, делящихся на $13$, но не на $2$;
• $4596$ остальных чисел.

Если один элемент пары делится на $26$, то второй элемент может быть любым другим числом последовательности.

Количество таких пар:

$397\cdot(10000-397)+\dfrac{397\cdot396}{2}$
$=397\cdot9603+78606$
$=3890997$.

Также подходят пары, в которых одно число делится на $2$, но не на $13$, а второе делится на $13$, но не на $2$.

Количество таких пар: $4620\cdot387=1787940$.

Общее количество подходящих пар: $3890997+1787940=5678937$.

Теперь найдём максимальную сумму.

Максимальное число, делящееся на $26$, равно $9984$.

В последовательности есть число $10000$.

Так как $9984=26\cdot384$, пара $9984$ и $10000$ подходит.

Её сумма: $9984+10000=19984$.

Для пар второго типа максимальными возможными элементами являются $10000$ и $9893$. Число $9893$ делится на $13$.

Их сумма: $10000+9893=19893$.

Следовательно, максимальная сумма подходящей пары равна $19984$.

Код на Python

a = [int(x) for x in open('17-28.txt')]

a26 = [x for x in a if x % 26 == 0]
a2 = [x for x in a if x % 2 == 0 and x % 13 != 0]
a13 = [x for x in a if x % 13 == 0 and x % 2 != 0]
a0 = [x for x in a if x % 2 != 0 and x % 13 != 0]

n26 = len(a26)
n2 = len(a2)
n13 = len(a13)

count = (
    n26 * (len(a) - n26)
    + n26 * (n26 - 1) // 2
    + n2 * n13
)

sums = []

if len(a26) >= 2:
    x = sorted(a26, reverse=True)
    sums.append(x[0] + x[1])

if a26 and a2:
    sums.append(max(a26) + max(a2))

if a26 and a13:
    sums.append(max(a26) + max(a13))

if a26 and a0:
    sums.append(max(a26) + max(a0))

if a2 and a13:
    sums.append(max(a2) + max(a13))

max_sum = max(sums)

print(count, max_sum)

Программа выводит:

5678937 19984