Разборы · ЕГЭ, задание 25

Задание 25 ЕГЭ по информатике: делители и маски чисел

Что проверяет задание

В задании 25 нужно написать программу, которая перебирает большой диапазон натуральных чисел и находит числа с заданными свойствами: подходящие под маску, с определённым набором делителей, произведения простых множителей. В ответ записывают таблицу: число и связанное с ним значение. 1 балл — только за полностью верную таблицу.

Что нужно знать

• Маска: «?» — ровно одна цифра, «*» — любая последовательность цифр, в том числе пустая. Функция fnmatch(str(n), маска) из модуля fnmatch проверяет именно это.
• Если число должно делиться на d, перебирайте только кратные d: range(d, предел + 1, d) — в d раз быстрее.
• Делители числа ищут до √n: каждый делитель i даёт пару n // i.

def divisors(n):
    d = set()
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            d |= {i, n // i}
    return sorted(d)

print(divisors(36))           # [1, 2, 3, 4, 6, 9, 12, 18, 36]

Как решать

1. Определите диапазон перебора и сузьте его: кратные, числа с нужным количеством цифр.
2. Проверьте сначала «дешёвые» условия (маска, остаток), и только потом «дорогие» (делители, простота).
3. Оцените время: 10⁷ простых проверок Python делает за несколько секунд, 10⁹ — уже слишком долго.

Пример из демоверсии 2027

Среди натуральных чисел, не превышающих 10¹⁰, найдите все числа, соответствующие маске 3?12?14*5 и делящиеся на 1917. Запишите их в порядке возрастания и рядом — частные от деления на 1917.

from fnmatch import fnmatch

for n in range(1917, 10**10 + 1, 1917):          # только кратные 1917
    if fnmatch(str(n), "3?12?14*5"):
        print(n, n // 1917)

Программа перебирает около 5 миллионов чисел и работает несколько секунд. Ответ:

351261495 183235
3212614035 1675855
3412614645 1780185
3712414275 1936575
3912414885 2040905

Можно и иначе: в маске 8 обязательных цифр, а числа не длиннее 10 цифр, значит, «*» — это от 0 до 2 цифр. Все числа по маске можно перебрать напрямую через itertools.product — их около 11 тысяч.

Типичные ошибки

• Путают «?» и «*»: «?» — ровно одна цифра, «*» может быть пустой.
• Перебирают все числа подряд до 10¹⁰ — программа не успевает.
• Записывают не то во втором столбце: частное, делитель, количество делителей — читайте условие.
• Пропускают строку таблицы — балл ставится только за полностью совпавший ответ.

Потренироваться: задание 25 новые варианты с проверкой ответа