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

В этой задаче элементы пары не обязаны стоять рядом. Нужно рассмотреть любые два различных элемента последовательности.

Чтобы произведение двух чисел делилось на $14$, в нём одновременно должны присутствовать множители $2$ и $7$.

Разделим числа на группы. В файле получаем:

• $n_{14}=683$ — делятся на $14$;
• $n_2=4262$ — делятся на $2$, но не делятся на $7$;
• $n_7=695$ — делятся на $7$, но не делятся на $2$;
• остальных чисел: $10000-683-4262-695=4360$.

Всего различных неупорядоченных пар: $\dfrac{10000\cdot9999}{2}=49995000$.

Найдём количество пар, произведение которых кратно $14$, а затем вычтем их из общего количества.

Если хотя бы одно число делится на $14$, произведение пары обязательно делится на $14$. Таких пар:

$683\cdot(10000-683)+\dfrac{683\cdot682}{2}$
$=683\cdot9317+232903$
$=6596414$.

Кроме того, произведение делится на $14$, если одно число делится на $2$, но не на $7$, а второе делится на $7$, но не на $2$.

Таких пар: $4262\cdot695=2962090$.

Значит, количество пар, произведение которых не кратно $14$: $49995000-6596414-2962090=40436496$.

Теперь найдём максимальную сумму подходящей пары.

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

Проверим произведение: $10000\bmod14=4$, $9999\bmod14=3$, поэтому $(10000\cdot9999)\bmod14=12\ne0$.

Следовательно, эта пара подходит.

Её сумма: $10000+9999=19999$.

Код на Python

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

n = len(a)

n14 = sum(x % 14 == 0 for x in a)
n2 = sum(x % 2 == 0 and x % 7 != 0 for x in a)
n7 = sum(x % 7 == 0 and x % 2 != 0 for x in a)

all_pairs = n * (n - 1) // 2

bad1 = n14 * (n - n14) + n14 * (n14 - 1) // 2
bad2 = n2 * n7

count = all_pairs - bad1 - bad2

a0 = sorted(
    [x for x in a if x % 2 != 0 and x % 7 != 0],
    reverse=True
)
a2 = sorted(
    [x for x in a if x % 2 == 0 and x % 7 != 0],
    reverse=True
)
a7 = sorted(
    [x for x in a if x % 7 == 0 and x % 2 != 0],
    reverse=True
)

sums = []

if len(a0) >= 2:
    sums.append(a0[0] + a0[1])

if len(a2) >= 2:
    sums.append(a2[0] + a2[1])

if len(a7) >= 2:
    sums.append(a7[0] + a7[1])

if a0 and a2:
    sums.append(a0[0] + a2[0])

if a0 and a7:
    sums.append(a0[0] + a7[0])

max_sum = max(sums)

print(count, max_sum)

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

40436496 19999