ЕГЭ. Информатика. 27 задание.

Вариант 2. 

Компьютер наземной станции слежения получает от объектов-самолётов, находящихся в зоне её работы, идентификационные сигналы, представляющие собой последовательность из N целых положительных чисел. Каждый объект направляет на наземную станцию уникальное число, т. е. все числа в получаемой станцией последовательности различны. Обработка сигнала представляет собой рассмотрение всех пар различных элементов последовательности, при этом элементы пары не обязаны быть переданы непосредственно друг за другом, порядок элементов в паре не важен. Считается, что возникла одна критическая ситуация, если произведение элементов некоторой пары кратно 58.

Необходимо определить общее количество возникших критических ситуаций.

Пояснение:

Произведение двух чисел делится на 58, если выполнено одно из следующих условий (условия не могут выполняться одновременно).

A. Оба сомножителя делятся на 58.

Б. Один из сомножителей делится на 58, а другой не делится.

B. Ни один из сомножителей не делится на 58, но один сомножитель делится на 2, а другой — на 29.

Почему именно 2 и 29?

Берем два делителя числа 58, произведение которых дает число 58: 2*29 = 58. При этом одно из них — наименьший делитель (в нашем случае 2), а другой, не должен делиться на первый найденный делитель (29/2 <> 0).

Условие делимости произведения на 58 можно сформулировать проще, например так:

(один из сомножителей делится на 58)

                    ИЛИ

(один сомножитель делится на 2, а другой — на 29)

Но в этом случае пара сомножителей может удовлетворять обоим условиям, что затруднит подсчёт количества пар.

При вводе чисел можно определять, делится ли каждое из них на 58, 2 и 29, и подсчитывать следующие значения:

n58 — количество чисел, кратных 58;

n29 —количество чисел, кратных 29, но не кратных 2 и 58;

n2 — количество чисел, кратных 2, но не кратных 29 и 58.

Сами числа при этом можно не хранить. Каждое число учитывается не более чем в одном из счётчиков.

Количество пар, удовлетворяющих условию А, можно вычислить по формуле n58*(n58 — 1)/2.

Количество пар, удовлетворяющих условию Б, можно вычислить по формуле n58*(N — n58).

Количество пар, удовлетворяющих условию В, можно вычислить по формуле n2 * n29.

Поэтому искомое количество пар вычисляется по формуле:

n58 * (n58 — 1)/2 + n58 * (N — n58) + n2 * n29

n=int(input())

n58,n29,n2=0,0,0

for i in range(n):

    a=int(input())

    if a % 28 == 0:

        n58+=1

    elif a % 29 == 0:

        n29+=1

    elif a % 2 == 0:

        n2+=1

k58=n58 * (n58-1) // 2 + n58 * (n-n58) + n2 * n29

print(k58)