Задача к ЕГЭ по информатике на тему «Макс/мин, кол-во пар, произведение кратно/не кратно» №2

Просмотров 9 Комментарии 0

Имеется набор данных из $N$ целых чисел. Рассматриваются все пары различных элементов последовательности. Необходимо определить количество пар, произведение которых не будет кратно $144$ .

В первой строке входных данных задаётся количество чисел $N$ $(1 ≤ N ≤ 10000)$ . В каждой из последующих $N$ строк записано одно целое положительное число, не превышающее $10$ $000$ .

Пример входных данных:

$5$

$12$

$11$

$13$

Выходные данные для приведённого выше примера: $7$

В ответе укажите два числа: сначала значение искомого количества для файла $A$ , затем для файла $B$ .

Решение 1 (неэффективное)

f = open("27A.txt")
n = int(f.readline())
a = [int(f.readline()) for x in range(n)]
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        if (a[i] * a[j]) % 144 != 0:
            ans += 1
print(ans)

Решение 2 (эффективное)

def dels(x):
    ans = []
    for i in range(1, x+1):
        if x % i == 0:
            ans += [i]
    return ans

a = dels(144)[::-1]
mask = [0]*145

n = int(input())

for i in range(n):
    x = int(input())
    for j in a:
        if x % j == 0:
            mask[j] += 1
            break

ans = 0
for i in range(len(a)):
    for j in range(i+1, len(a)):
        if a[i]*a[j] % 144 != 0:
            ans += mask[a[i]]*mask[a[j]]

for i in range(len(a)):
    if a[i]**2 % 144 != 0:
        ans += mask[a[i]]*(mask[a[i]]-1) // 2

print(ans)

Ответ: 190 11846101