Задание 27 ЕГЭ по информатике · 902B84

На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности: элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен. Необходимо определить количество пар, для которых произведение элементов делится на 26.
В первой строке входных данных задаётся количество чисел N (1≤N≤1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна напечатать одно число: количество пар, в которых произведение элементов кратно 26.
Пример входных данных:
4
2
6
13
39
Пример выходных данных для приведённого выше примера входных данных:
4
Из четырёх заданных чисел можно составить 6 попарных произведений: 2⋅6, 2⋅13, 2⋅39, 6⋅13, 6⋅39, 13⋅39. Из них на 26 делятся 4 произведения: 2⋅13=26, 2⋅39=78, 6⋅13=78, 6⋅39=234.
Требуется написать эффективную по времени и по памяти программу для решения описанной задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N.
Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.

1. Так как 26=2⋅13, произведение двух чисел делится на 26, если в произведении присутствуют множители 2 и 13.
26=2⋅13

2. Число, кратное 26, образует подходящую пару с любым другим числом. Поэтому при чтении такого числа к ответу добавляется количество всех уже прочитанных чисел.

3. Число, кратное 2, но не кратное 13, образует подходящую пару с числами, кратными 13, но не кратными 2. Аналогично, число, кратное только 13, образует пары с ранее прочитанными числами, кратными только 2.

4. Храним только четыре счётчика: количество ранее прочитанных чисел, количество чисел, кратных только 2, количество чисел, кратных только 13, и общее количество прочитанных чисел. Алгоритм выполняется за O(N) времени и использует O(1) памяти.

5. Программа на Python 3. При чтении очередного числа сначала учитываются пары с уже обработанными числами, затем обновляются счётчики.

6. Код программы:
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)