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

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

1. Разложим число 58 на простые множители: 58=2⋅29. Произведение двух чисел делится на 58, если в произведении есть множитель 2 и множитель 29.

2. Для каждого входного числа определим два булевых признака: наличие множителя 2 и наличие множителя 29. Поэтому все числа можно разделить на четыре типа: не делится ни на 2, ни на 29; делится только на 2; делится только на 29; делится и на 2, и на 29.

3. Будем обрабатывать числа по одному и хранить только четыре счётчика количества уже обработанных чисел каждого типа. Для текущего числа переберём четыре типа предыдущих чисел и проверим условие: хотя бы одно из двух чисел делится на 2 и хотя бы одно из них делится на 29.

4. Каждое подходящее предыдущее число образует одну новую пару с текущим числом. После подсчёта добавим текущий элемент в соответствующий счётчик.

5. Алгоритм выполняется за O(N) времени, поскольку для каждого числа проверяются только четыре типа. Дополнительная память постоянна и равна O(1).