Ответ: Подсчёт пар, кратных 14
Алгоритм с тремя счётчиками работает за $O(N)$ по времени и $O(1)$ по памяти. Подходит реализация на Python 3, приведённая в решении.
У этого задания официального ключа нет, поэтому ответ получен в разборе и с ключом не сверен. Перед тем как заучивать результат, пройдите выкладки — там видно, откуда взялось каждое число.
На вход программы поступает последовательность из $N$ целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности: порядок элементов в паре не важен. Необходимо определить количество пар, для которых произведение элементов делится на $14$.
В первой строке входных данных задаётся количество чисел $N$ ($1 \leq N \leq 1000$). В каждой из последующих $N$ строк записано одно целое положительное число, не превышающее $10\,000$. Программа должна вывести количество пар, в которых произведение элементов кратно $14$.
Пример входных данных:
4
2
6
7
21
Пример выходных данных:
4
Требуется написать эффективную по времени и по памяти программу. Алгоритм должен работать за время $O(N)$, а используемая память не должна зависеть от $N$ и не должна превышать 1 килобайт. Перед текстом программы необходимо кратко описать алгоритм решения и указать использованный язык программирования и его версию.
Где здесь ошибаются
Перебирать все пары, получая сложность $O(N^2)$.
Учитывать только пары, в которых одно число кратно $14$, хотя множители $2$ и $7$ могут находиться в разных числах.
Не вычитать числа, кратные $14$, когда текущее число также кратно $14$: такие пары считаются дважды.
Хранить всю последовательность, нарушая требование постоянного объёма памяти.