Задание 25: Обработка целочисленной информации

Типичная формулировка: даётся определение маски (символ «?» — одна произвольная цифра, символ «» — произвольная последовательность цифр, включая пустую), приводится конкретная маска вида «12345?7?8» или «1?49341», указывается верхняя граница (например, $10^9$ или $10^{10}$) и делитель (23, 2023, 3123 и т.п.). Нужно найти все натуральные числа, соответствующие маске, не превышающие границу и кратные делителю, а затем выписать их в порядке возрастания. Иногда дополнительно требуется указать частное от деления каждого числа на делитель.

…

• Позиционная запись: число длиной $n$ цифр записывается как $N=\sum_{i=0}^{n-1} d_i\cdot 10^i$, где $d_{n-1}$ — старшая цифра.
• «?» задаёт ровно одну цифру $0$–$9$ в фиксированной позиции; «*» задаёт произвольную (в том числе пустую) последовательность цифр, то есть переменную длину блока.
• Длина числа по маске равна сумме длин всех фиксированных символов и выбранной длины каждого блока «*».
• Свойства остатков: $(a+b)\bmod m=\big((a\bmod m)+(b\bmod m)\big)\bmod m$, $(a\cdot b)\bmod m=\big((a\bmod m)\cdot(b\bmod m)\big)\bmod m$.
• Линейное сравнение $ax\equiv b\pmod m$ имеет решение, если $\gcd(a,m)$ делит $b$; при $\gcd(a,m)=1$ решение единственно по модулю $m$ и находится через обратный элемент $a^{-1}\bmod m$ (расширенный алгоритм Евклида).
• Признаки делимости на 2, 3, 5, 9, 10, 11 полезны для быстрой проверки отдельных кандидатов.
• Верхняя граница числа жёстко ограничивает максимально возможную длину числа, а значит и допустимую длину блока «*» — это нужно посчитать первым делом.

1. Определить фиксированные и переменные части маски: сколько цифр задано жёстко, где стоят «?», где — «*».
2. Из ограничения на число вычислить, какие длины блока «*» вообще допустимы.
3. Для каждой допустимой длины записать число как сумму: фиксированная часть слева × степень десяти + значение блока × степень десяти + фиксированная часть справа, с учётом неизвестных «?» как переменных.
4. Привести выражение к виду $N\equiv0\pmod m$ и вычислить нужные степени десяти по модулю $m$.
5. Если неизвестных немного — перебрать их значения напрямую; если есть блок «*» — решить линейное сравнение относительно него.
6. Отобрать решения, лежащие в допустимом диапазоне: для «?» это $0$–$9$, для блока «*» — $0$–$10^k-1$, включая случаи с нулями внутри блока.
7. Собрать все числа, отсортировать по возрастанию, при необходимости посчитать частное. …