Решение: Подсчёт пар с делимостью
На вход программы поступает последовательность из $N$ целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 5 (разница в индексах элементов пары должна быть 5 или более, порядок элементов в паре неважен). Необходимо определить количество таких пар, для которых произведение элементов делится на 17.
В первой строке входных данных задаётся количество чисел $N$ ($5 \leq N \leq 1000$). В каждой из последующих $N$ строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 5, в которых произведение элементов кратно 17.
Пример входных данных:
8
34
2
3
5
4
6
7
17
Пример выходных данных для приведённого выше примера входных данных:
5
Пояснение: из восьми заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений: $34 \cdot 6$, $34 \cdot 7$, $34 \cdot 17$, $2 \cdot 7$, $2 \cdot 17$, $3 \cdot 17$. Из них на 17 делятся 5 произведений.
Требуется написать эффективную по времени и памяти программу. Время работы должно быть не более линейным по $N$, а память для хранения переменных не должна превышать 1 килобайта и не должна увеличиваться с ростом $N$.
Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Решение по шагам
7 шаговТак как 17 — простое число, произведение двух чисел делится на 17 тогда и только тогда, когда хотя бы один множитель делится на 17.
$$17 \mid (a_i a_j) \Longleftrightarrow 17 \mid a_i \lor 17 \mid a_j$$При обработке элемента с индексом i допустимыми являются элементы с индексами не больше i-5. Поэтому перед обработкой текущего элемента добавляем в множество допустимых элемент, прочитанный пять шагов назад.
Храним количество всех допустимых элементов и количество допустимых элементов, кратных 17. Если текущий элемент кратен 17, он образует подходящую пару с каждым допустимым элементом. Иначе он образует подходящую пару только с допустимыми элементами, кратными 17.
Для хранения пяти последних значений используется циклическая очередь размера 5. Все остальные данные обрабатываются потоково, поэтому дополнительная память не зависит от N.
Программа на Python 3.11:
from collections import deque
n = int(input())
last = deque()
all_old = 0
mult17_old = 0
answer = 0
for _ in range(n):
x = int(input())
if len(last) == 5:
y = last.popleft()
all_old += 1
if y % 17 == 0:
mult17_old += 1
if x % 17 == 0:
answer += all_old
else:
answer += mult17_old
last.append(x)
print(answer)
Каждый элемент добавляется в очередь и удаляется из неё один раз. Поэтому время работы имеет сложность O(N), а дополнительная память — O(1), поскольку очередь содержит не более пяти элементов.
$$T(N)=O(N),\quad M(N)=O(1)$$Алгоритм с очередью из пяти последних элементов, сложность O(N) по времени и O(1) по дополнительной памяти.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Учитывают элементы на расстоянии менее 5.
Проверяют только текущий элемент на кратность 17 и забывают о предыдущем.
Хранят всю последовательность, нарушая требование постоянной дополнительной памяти.
Используют двойной перебор всех пар, получая сложность O(N^2).
Добавляют элемент, находящийся ровно на расстоянии 5, слишком поздно или слишком рано.