Каталог: Задание №25. Обработка целочисленной информации (Маски и делители)

Банк задач: 416 Формат ЕГЭ 2026 Повышенный (1 балл) 3-5 мин Шаблоны решений на Python

Выберите номер задания ЕГЭ:

№1 №2 №3 №4 №5 №6 №7 №8 №9 №10 №11 №12 №13 №14 №15 №16 №17 №18 №19 №20 №21 №22 №23 №24 №25 №26 №27

Спецификация и суть задания №25

Тема кодификатора Функция fnmatch для масок (? и *), поиск делителей за O(sqrt(N)) и простые числа

Сложность и баллы Повышенный (1 балл)

Рекомендуемое время 3-5 мин

Инструменты решения Python fnmatch, Поиск делителей за O(sqrt(N))

Поиск чисел по маске (символы ? — ровно один, * — любое количество) или чисел с особыми свойствами делителей.

Основные прототипы и разновидности

Тип 1: Поиск чисел по маске, кратных K (fnmatch)

Перебор range(0, 10**10, K) с проверкой fnmatch(str(n), mask).

Тип 2: Поиск делителей числа за O(sqrt(N))

Сбор пар d и n // d до int(n**0.5).

Теоретический фундамент и алгоритмы

1. Модуль fnmatch для проверки масок:

? — ровно один любой символ.
* — любая (в том числе пустая) последовательность символов.
from fnmatch import fnmatch; if fnmatch(str(n), '12*34?5'): ...

2. Эффективный поиск делителей за $O(\sqrt{N})$:

def get_divisors(n):
    divs = set()
    for d in range(1, int(n**0.5) + 1):
        if n % d == 0:
            divs.add(d)
            divs.add(n // d)
    return sorted(divs)

Лайфхаки и фишки для ускорения

Совет

Всегда шагайте с шагом делителя range(div, limit, div) — код выполнится за 0.1 секунды!

Частые ошибки и экзаменационные ловушки

Ошибка: Перебирать ВСЕ числа с шагом 1: for n in range(10**9):
1 миллиард итераций будет выполняться 15 минут!

Правильно: Шагать сразу с шагом делителя: for n in range(div, 10**9, div):

ГРОБ №25: Число делителей у чисел порядка 10^12

Числа слишком большие для наивного перебора.

Алгоритм решения: Генерируйте числа напрямую по маске, перебирая цифры на месте `?` и `*`.

Практические задачи из банка КИМ (Всего: 416)

Решать в песочнице СмартКИМ

Задача #9007 №25 ЕГЭ