Ответ: Пары с произведением, кратным 26
Алгоритм имеет сложность $O(N)$ по времени и $O(1)$ по памяти; приведённая программа корректно подсчитывает количество пар с произведением, кратным $26$.
У этого задания официального ключа нет, поэтому ответ получен в разборе и с ключом не сверен. Перед тем как заучивать результат, пройдите выкладки — там видно, откуда взялось каждое число.
На вход программы поступает последовательность из $N$ целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности: элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен. Необходимо определить количество пар, для которых произведение элементов делится на $26$.
В первой строке входных данных задаётся количество чисел $N$ ($1 \leq N \leq 1000$). В каждой из последующих $N$ строк записано одно целое положительное число, не превышающее $10\,000$.
В качестве результата программа должна напечатать одно число: количество пар, в которых произведение элементов кратно $26$.
Пример входных данных:
4
2
6
13
39
Пример выходных данных для приведённого выше примера входных данных:
4
Из четырёх заданных чисел можно составить 6 попарных произведений: $2 \cdot 6$, $2 \cdot 13$, $2 \cdot 39$, $6 \cdot 13$, $6 \cdot 39$, $13 \cdot 39$. Из них на $26$ делятся 4 произведения: $2 \cdot 13 = 26$, $2 \cdot 39 = 78$, $6 \cdot 13 = 78$, $6 \cdot 39 = 234$.
Требуется написать эффективную по времени и по памяти программу для решения описанной задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел $N$ в $k$ раз время работы программы увеличивается не более чем в $k$ раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом $N$.
Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Где здесь ошибаются
Перебирать все пары, получая сложность $O(N^2)$.
Относить числа, кратные $26$, одновременно к группам «только кратные $2$» или «только кратные $13$».
Не учитывать, что число, кратное $26$, образует подходящую пару с любым другим числом.
Хранить всю последовательность, нарушая требование постоянного объёма памяти.