Решение: Пары с произведением, кратным 38
На вход программы поступает последовательность из $N$ целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности: элементы пары не обязаны стоять рядом, порядок элементов в паре не важен. Необходимо определить количество пар, для которых произведение элементов делится на $38$.
В первой строке входных данных задаётся количество чисел $N$ ($1 \le N \le 1000$). В каждой из последующих $N$ строк записано одно целое положительное число, не превышающее $10\,000$.
В качестве результата программа должна напечатать одно число — количество пар, в которых произведение элементов кратно $38$.
Пример входных данных:
$4$
$2$
$6$
$19$
$57$
Пример выходных данных:
$4$
Из четырёх заданных чисел можно составить $6$ попарных произведений: $2\cdot6$, $2\cdot19$, $2\cdot57$, $6\cdot19$, $6\cdot57$, $19\cdot57$. На $38$ делятся произведения $2\cdot19$, $2\cdot57$, $6\cdot19$, $6\cdot57$.
Требуется написать эффективную по времени и по памяти программу. Программа считается эффективной по времени, если при увеличении количества исходных чисел $N$ в $k$ раз время её работы увеличивается не более чем в $k$ раз. Программа считается эффективной по памяти, если память для хранения всех переменных не превышает $1$ килобайта и не увеличивается с ростом $N$.
Перед текстом программы необходимо кратко описать алгоритм решения, указать использованный язык программирования и его версию.
Решение по шагам
6 шаговРазложим число $38$ на простые множители: $38 = 2\cdot19$. Произведение двух чисел делится на $38$, если в нём присутствуют множители $2$ и $19$.
Во время последовательного чтения чисел будем хранить только четыре счётчика: количество уже прочитанных чисел, количество чисел, кратных $2$, количество чисел, кратных $19$ и количество чисел, кратных $38$. Эти счётчики занимают постоянный объём памяти.
Если очередное число $x$ кратно $38$, то оно образует подходящую пару с каждым предыдущим числом. Если $x$ кратно $2$, но не кратно $19$, ему в пару нужны предыдущие числа, кратные $19$. Если $x$ кратно $19$, но не кратно $2$, ему в пару нужны предыдущие числа, кратные $2$. В остальных случаях подходящих пар нет.
После подсчёта пар обновляем соответствующие счётчики. Каждое число обрабатывается один раз, поэтому время работы имеет порядок $O(N)$, а дополнительная память — $O(1)$.
Программа на Python 3. Для хранения ответа используется целое число, так как максимальное количество пар равно $\frac{N(N-1)}{2}$.
```python
n = int(input())
seen = 0
count_2 = 0
count_19 = 0
count_38 = 0
answer = 0
for _ in range(n):
x = int(input())
if x % 38 == 0:
answer += seen
elif x % 2 == 0:
answer += count_19
elif x % 19 == 0:
answer += count_2
seen += 1
if x % 2 == 0:
count_2 += 1
if x % 19 == 0:
count_19 += 1
if x % 38 == 0:
count_38 += 1
print(answer)
```
Алгоритм работает за $O(N)$ по времени и использует $O(1)$ дополнительной памяти; приведённая программа на Python 3 корректно подсчитывает количество пар с произведением, кратным $38$.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Перебирать все пары, получая сложность $O(N^2)$.
Считать достаточным наличие делимости одного из чисел на $38$, не учитывая пары чисел, одно из которых кратно $2$, а другое — $19$.
Обновлять счётчики до подсчёта пар, из-за чего число может образовать пару само с собой.
Хранить всю последовательность, нарушая требование постоянного объёма памяти.
Не учитывать числа, кратные одновременно $2$ и $19$.