Решение: Подсчёт пар с произведением 74
На вход программы поступает последовательность из $N$ целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности: элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен. Необходимо определить количество пар, для которых произведение элементов делится на $74$.
В первой строке входных данных задаётся количество чисел $N$ ($1 \leq N \leq 1000$). В каждой из последующих $N$ строк записано одно целое положительное число, не превышающее $10000$.
В качестве результата программа должна напечатать одно число: количество пар, в которых произведение элементов кратно $74$.
Пример входных данных:
$4$
$2$
$6$
$37$
$111$
Пример выходных данных для приведённого выше примера входных данных:
$4$
Из четырёх заданных чисел можно составить $6$ попарных произведений: $2 \cdot 6$, $2 \cdot 37$, $2 \cdot 111$, $6 \cdot 37$, $6 \cdot 111$, $37 \cdot 111$. Из них на $74$ делятся $4$ произведения: $2 \cdot 37 = 74$, $2 \cdot 111 = 222$, $6 \cdot 37 = 222$, $6 \cdot 111 = 666$.
Требуется написать эффективную по времени и по памяти программу. При увеличении количества исходных чисел $N$ в $k$ раз время работы программы должно увеличиваться не более чем в $k$ раз. Память, необходимая для хранения всех переменных программы, не должна превышать $1$ килобайта и не должна увеличиваться с ростом $N$.
Перед текстом программы необходимо кратко описать алгоритм решения, указать использованный язык программирования и его версию.
Решение по шагам
5 шаговПредставим число $74$ как произведение взаимно простых множителей:
$$74 = 2 \cdot 37$$При последовательной обработке очередного числа достаточно знать количество ранее обработанных чисел четырёх типов: всех чисел; чётных чисел; чисел, кратных $37$; чисел, кратных $74$.
Если текущее число кратно $74$, его произведение с любым предыдущим числом кратно $74$. Если число кратно $37$, но нечётно, ему в пару нужно предыдущее чётное число. Если число чётное, но не кратно $37$, ему в пару нужно предыдущее число, кратное $37$. Для остальных чисел подходящих пар нет.
После подсчёта подходящих пар обновляются счётчики типов текущего числа. Все операции выполняются за постоянное время для каждого элемента.
Алгоритм имеет временную сложность $O(N)$ и использует $O(1)$ дополнительной памяти. Например, реализация на Python 3:
$$n = int(input()) all_count = 0 even_count = 0 mult37_count = 0 mult74_count = 0 answer = 0 for _ in range(n): x = int(input()) if x % 74 == 0: answer += all_count elif x % 37 == 0: answer += even_count elif x % 2 == 0: answer += mult37_count all_count += 1 if x % 2 == 0: even_count += 1 if x % 37 == 0: mult37_count += 1 if x % 74 == 0: mult74_count += 1 print(answer)$$Программа должна использовать однопроходный подсчёт с четырьмя счётчиками; сложность — $O(N)$ по времени и $O(1)$ по дополнительной памяти.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Перебирать все пары, получая сложность $O(N^2)$.
Учитывать только пары «чётное число и число, кратное $37$», не обработав числа, кратные $74$.
Добавлять текущий элемент в счётчики до подсчёта пар, из-за чего число может образовать пару само с собой.
Хранить всю последовательность, хотя для решения достаточно нескольких счётчиков.