Решение: Пары с произведением, кратным 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$.
Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Решение по шагам
6 шаговТак как $26 = 2 \cdot 13$, произведение двух чисел делится на $26$, если в произведении присутствуют множители $2$ и $13$.
$$26 = 2 \cdot 13$$Число, кратное $26$, образует подходящую пару с любым другим числом. Поэтому при чтении такого числа к ответу добавляется количество всех уже прочитанных чисел.
Число, кратное $2$, но не кратное $13$, образует подходящую пару с числами, кратными $13$, но не кратными $2$. Аналогично, число, кратное только $13$, образует пары с ранее прочитанными числами, кратными только $2$.
Храним только четыре счётчика: количество ранее прочитанных чисел, количество чисел, кратных только $2$, количество чисел, кратных только $13$, и общее количество прочитанных чисел. Алгоритм выполняется за $O(N)$ времени и использует $O(1)$ памяти.
Программа на Python 3. При чтении очередного числа сначала учитываются пары с уже обработанными числами, затем обновляются счётчики.
Код программы:
n = int(input())
answer = 0
total = 0
only_2 = 0
only_13 = 0
for _ in range(n):
x = int(input())
if x % 26 == 0:
answer += total
elif x % 2 == 0:
answer += only_13
elif x % 13 == 0:
answer += only_2
total += 1
if x % 2 == 0 and x % 13 != 0:
only_2 += 1
elif x % 13 == 0 and x % 2 != 0:
only_13 += 1
print(answer)
Алгоритм имеет сложность $O(N)$ по времени и $O(1)$ по памяти; приведённая программа корректно подсчитывает количество пар с произведением, кратным $26$.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Перебирать все пары, получая сложность $O(N^2)$.
Относить числа, кратные $26$, одновременно к группам «только кратные $2$» или «только кратные $13$».
Не учитывать, что число, кратное $26$, образует подходящую пару с любым другим числом.
Хранить всю последовательность, нарушая требование постоянного объёма памяти.