Решение: Подсчёт пар по делимости
На вход программы поступает последовательность из $N$ целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности: элементы пары не обязаны стоять рядом, порядок элементов в паре не важен. Необходимо определить количество пар, для которых произведение элементов делится на $58$.
В первой строке входных данных задаётся количество чисел $N$ ($1 \leq N \leq 1000$). В каждой из последующих $N$ строк записано одно целое положительное число, не превышающее $10\,000$.
В качестве результата программа должна напечатать одно число — количество пар, в которых произведение элементов кратно $58$.
Требуется написать эффективную по времени и по памяти программу. Программа считается эффективной по времени, если при увеличении количества исходных чисел $N$ в $k$ раз время её работы увеличивается не более чем в $k$ раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом $N$.
Перед текстом программы необходимо кратко описать алгоритм решения, указать использованный язык программирования и его версию.
Пример входных данных: $4, 2, 6, 29, 87$. Пример выходных данных: $4$.
Решение по шагам
5 шаговРазложим число $58$ на простые множители: $58 = 2 \cdot 29$. Произведение двух чисел делится на $58$, если в произведении есть множитель $2$ и множитель $29$.
Для каждого входного числа определим два булевых признака: наличие множителя $2$ и наличие множителя $29$. Поэтому все числа можно разделить на четыре типа: не делится ни на $2$, ни на $29$; делится только на $2$; делится только на $29$; делится и на $2$, и на $29$.
Будем обрабатывать числа по одному и хранить только четыре счётчика количества уже обработанных чисел каждого типа. Для текущего числа переберём четыре типа предыдущих чисел и проверим условие: хотя бы одно из двух чисел делится на $2$ и хотя бы одно из них делится на $29$.
Каждое подходящее предыдущее число образует одну новую пару с текущим числом. После подсчёта добавим текущий элемент в соответствующий счётчик.
Алгоритм выполняется за $O(N)$ времени, поскольку для каждого числа проверяются только четыре типа. Дополнительная память постоянна и равна $O(1)$.
Программа на Python 3 использует четыре счётчика типов чисел, работает за $O(N)$ времени и использует $O(1)$ дополнительной памяти.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Проверять все пары напрямую, получая сложность $O(N^2)$.
Считать достаточным наличие множителя $2$ или только множителя $29$.
Увеличивать счётчик текущего типа до подсчёта пар с текущим числом, из-за чего число может образовать пару само с собой.
Хранить всю последовательность, хотя для решения достаточно четырёх счётчиков.