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

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

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

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

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


Входные данные	Выходные данные

6	3
3
2
9
33
11
6

Переборное решение

f = open("27.txt")
n = int(f.readline())
a = [int(x) for x in f]

ans = 0
k = 66

for i in range(n):
    for j in range(i + 1, n):
        if a[i] * a[j] % k == 0:
            ans += 1

print(ans)

Статическое решение

f = open("27.txt")
n = int(f.readline())

ans = 0  # Счётчик пар для ответа
divs = [x for x in range(1, 67) if 66 % x == 0]  # Делители числа 66
k = [0] * (66 + 1)  # Список, хранящий количество чисел, кратных соответствующему делителю

for i in range(n):
    x = int(f.readline())
    maxDiv = 0  # Максимальный делитель, которому кратно число x
    for d in divs:
        if x % d == 0:
            maxDiv = d
    k[maxDiv] += 1

# Перебор пар делителей
for a in range(len(divs)):
    for b in range(a, len(divs)):  # Начинаем с a, чтобы не перебирать одинаковые пары по 2 раза
        if divs[a] * divs[b] % 66 == 0:
            if a == b:
                ans += k[divs[a]] * (k[divs[b]] - 1) // 2
            else:
                ans += k[divs[a]] * k[divs[b]]

print(ans)

Динамическое решение

f = open("27.txt")
n = int(f.readline())

ans = 0  # Счётчик пар для ответа
divs = [x for x in range(1, 67) if 66 % x == 0]  # Делители числа 66
k = [0] * (66 + 1)  # Список, хранящий количество чисел, кратных соответствующему делителю

for i in range(n):
    x = int(f.readline())
    maxDiv = 1
    for d in divs:
        if x * d % 66 == 0:
            ans += k[d]
        if x % d == 0:
            maxDiv = d
    k[maxDiv] += 1

print(ans)

Ответ: 16 3844763