Повышенный (1 балл)
Время: 3-5 мин
Python fnmatch
Поиск делителей за O(sqrt(N))
Все задачи №25 в каталоге
Задание №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
Запустить код в онлайн-песочницеБоевой шаблон решения на Python
from fnmatch import fnmatch
for n in range(161, 10 ** 8 + 1, 161):
if fnmatch(str(n), "12*4?65"):
print(n, n // 161)Типичные ошибки
✕ Не так
Ошибка: Перебирать ВСЕ числа с шагом 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 секунды!