Задание EGEINF3F7746: Делители, маски и отбор чисел

Решение.
Ищем все натуральные n, удовлетворяющие маске 12??15*6, ограничению n ≤ 10⁸ и делимости на 253.
Каждый знак «?» заменяется ровно одной десятичной цифрой. Звёздочка допускает пустую строку и строки с нулями в начале: эти нули находятся внутри записи числа и должны сохраняться.
Без звёздочки в маске 7 позиций, из них 2 обозначены знаком «?». Граница 10⁸ отдельно проверяется по маске и ей не соответствует. Все остальные допустимые числа содержат не более 8 цифр.
Поэтому длина замены «*» принимает все целые значения от 0 до 1. При длине k имеется 10² · 10ᵏ подстановок.
Общее число подстановок: 100 + 1000 = 1100.
Первый символ маски — фиксированная ненулевая цифра. Подстановки дают натуральные числа без ведущего нуля; различные наборы замен дают разные записи. Перебор длин и всех цифр охватывает каждое допустимое число.
Для каждого кандидата вычисляем частное и остаток при делении на 253. Оставляем ровно те числа, у которых остаток равен нулю, затем упорядочиваем их по числовому значению.
Найденные числа и проверка каждой строки:
n = 1278156: значения «?» слева направо: 7, 8; «*» = пустая строка.
253 · 5052 = 1278156; остаток 0.
n = 12531596: значения «?» слева направо: 5, 3; «*» = «9».
253 · 49532 = 12531596; остаток 0.
n = 12741586: значения «?» слева направо: 7, 4; «*» = «8».
253 · 50362 = 12741586; остаток 0.
n = 12951576: значения «?» слева направо: 9, 5; «*» = «7».
253 · 51192 = 12951576; остаток 0.
Проверены все 1100 подстановок и отдельно верхняя граница; найдено 4 подходящих чисел. Других замен маски в допустимом диапазоне нет.
Проверка результата.
Воспроизводимая программа Python:

from itertools import product
from fnmatch import fnmatchcase

mask = '12??15*6'
limit = 10 ** 8
divisor = 253
fixed = len(mask.replace('*', ''))
lengths = range(8 - fixed + 1) if '*' in mask else [0]
numbers = set()
for length in lengths:
    pattern = mask.replace('*', '?' * length)
    for digits in product('0123456789', repeat=pattern.count('?')):
        it = iter(digits)
        text = ''.join(next(it) if c == '?' else c for c in pattern)
        numbers.add(int(text))
if fnmatchcase(str(limit), mask):
    numbers.add(limit)
for n in sorted(numbers):
    quotient, remainder = divmod(n, divisor)
    if remainder == 0:
        print(n, quotient)

Результат: в каждой строке слева n, справа частное.
1278156 — 5052
12531596 — 49532
12741586 — 50362
12951576 — 51192
Ответ: (1278156; 5052), (12531596; 49532), (12741586; 50362), (12951576; 51192).