Задание EGEINFFB72C9: Самостоятельное написание алгоритма

Решение.
Язык: Python 3. Сначала читаем число элементов, затем по одному целому числу с каждой следующей строки. Всю последовательность сохранять не нужно. Пара всегда образована разными позициями; текущий элемент сравниваем с уже прочитанными, а состояние обновляем после проверки пары.
Число 58 = 2 · 29, где 29 — нечётное простое. Произведение кратно 58, если в двух множителях вместе присутствуют множители 2 и 29.
Разбиваем уже прочитанные числа на непересекающиеся группы. both — кратные обоим множителям; even — чётные, но не кратные p; prime — кратные p, но нечётные. Остальные числа не кратны ни одному множителю.
Если x кратно 58, оно образует подходящую пару с любым из i предыдущих элементов. Если x чётно, но не кратно 29, подходят prime + both прежних чисел. Если x нечётно и кратно 29, подходят even + both. Если x не кратно ни 2, ни 29, подходят только both.
Прибавляем соответствующее количество к answer. Ветка elif делает группы непересекающимися: кратное обоим множителям число не попадает одновременно в even и prime. Поэтому пары не дублируются.
После прибавления увеличиваем счётчик группы текущего числа. Это исключает пару числа с самим собой. Каждая допустимая пара учитывается ровно один раз — при чтении её более позднего элемента.
Для N = 1 ответ равен нулю. Если подходящих пар нет, answer также остаётся нулём. Входные числа по условию различны; сохранять сами значения для проверки различия не требуется.
Время O(N), память O(1): три счётчика классов, накопитель ответа и несколько скалярных переменных. Данные программы существенно меньше 1 Кбайт и не растут с N.
Программа:

p = 29
n = int(input())
even = prime = both = 0
answer = 0
for i in range(n):
    x = int(input())
    if x % (2 * p) == 0:
        answer += i
        both += 1
    elif x % 2 == 0:
        answer += prime + both
        even += 1
    elif x % p == 0:
        answer += even + both
        prime += 1
    else:
        answer += both
print(answer)

Проверка на примере.
Входная последовательность: 2, 6, 29, 87.
Программа выводит: 4.
Подходящие пары в этом примере: (2, 29), (2, 87), (6, 29), (6, 87). Их количество — 4.
Обоснование полноты. Каждый новый элемент рассматривается как правый элемент пары. Состояние содержит достаточную информацию обо всех допустимых прежних элементах; выбранный партнёр оптимален либо счётчик даёт точное количество партнёров. После обновления это свойство сохраняется для следующей итерации. Значит, после конца ввода учтены все допустимые пары, без пропусков и повторного использования одной пары.
Ответ: Программа на Python 3 приведена в решении.