Повышенный (1 балл)
Время: 3-5 мин
Python fnmatch
Поиск делителей за O(sqrt(N))
Все задачи №{ topic_num } в каталоге
Задание №25. Обработка целочисленной информации (Маски и делители)
Тема: Функция fnmatch для масок (? и *), поиск делителей за O(sqrt(N)) и простые числа
Поиск чисел по маске (символы `?` — ровно один, `*` — любое количество) или чисел с особыми свойствами делителей.
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)Разновидности и прототипы задания на экзамене
Тип 1: Поиск чисел по маске, кратных K (fnmatch)
Перебор `range(0, 10**10, K)` с проверкой `fnmatch(str(n), mask)`.
Тип 2: Поиск делителей числа за O(sqrt(N))
Сбор пар `d` и `n // d` до `int(n**0.5)`.
Боевой шаблон решения на Python
Запустить код в онлайн-песочнице# === Боевой шаблон Задания №25 на Python ===
from fnmatch import fnmatch
# Тип 1: Поиск чисел по маске '12?4*56', кратных 3123:
mask = "12?4*56"
divisor = 3123
max_limit = 10**9
# Шагаем строго с шагом divisor (в 3123 раза быстрее!):
for n in range(divisor, max_limit, divisor):
if fnmatch(str(n), mask):
print(n, n // divisor)
# Тип 2: Поиск чисел с ровно 5 нетривиальными делителями:
def count_divs(n):
divs = []
for d in range(2, int(n**0.5) + 1):
if n % d == 0:
divs.append(d)
if d != n // d:
divs.append(n // d)
return sorted(divs)Анти-примеры (Типичные ошибки vs Как делать правильно)
Как делать НЕ надо:
Ошибка: Перебирать ВСЕ числа с шагом 1: for n in range(10**9):
1 миллиард итераций будет выполняться 15 минут!Как делать ПРАВИЛЬНО:
Правильно: Шагать сразу с шагом делителя: for n in range(div, 10**9, div):
ГРОБ
ГРОБ №25: Число делителей у чисел порядка 10^12
Числа слишком большие для наивного перебора.
Как обойти ловушку: Генерируйте числа напрямую по маске, перебирая цифры на месте `?` и `*`.
Лайфхаки и подводные камни на экзамене:
- Всегда шагайте с шагом делителя `range(div, limit, div)` — код выполнится за 0.1 секунды!