Задание 25 ЕГЭ по информатике: маска числа и поиск делителей

Что проверяет задание

Задание 25 проверяет умение работать с целыми числами в десятичной системе счисления без калькулятора: раскладывать число по разрядам, вычислять остатки от деления, решать простые линейные сравнения и аккуратно перебирать конечное число вариантов. Формально тема называется «обработка целочисленной информации», но по сути это алгебраически-комбинаторная задача: маска задаёт целое семейство чисел, и среди них нужно найти те, что делятся на заданное число без остатка, уложившись в ограничение по величине.

Здесь одновременно проверяются три навыка: понимание позиционной записи числа, работа с модульной арифметикой (остатки, свойства сложения и умножения по модулю) и системный перебор — умение свести большое или бесконечное множество вариантов к небольшому, которое можно проверить руками.

Как выглядит формулировка и сколько баллов

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

Задание оценивается в 2 первичных балла. Полный балл ставится только за полностью верный и полный список чисел (без лишних и без пропущенных), 1 балл — если допущена одна ошибка, 0 баллов — при большем числе ошибок. Поэтому важно не просто найти решения, но и убедиться, что перебраны все случаи, включая пустую подстановку для «*».

Что нужно знать

• Позиционная запись: число длиной $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. Разложение числа по разрядам. Маска без «*» превращается в линейную функцию от неизвестных цифр. Например, маска «5?3» даёт $N=500+10x+3$, где $x$ — цифра на месте «?».
2. Перебор по цифре «?». Она принимает всего 10 значений, поэтому для каждой неизвестной подставляют $0,\dots,9$ и проверяют остаток. Пример: маска «7?4», делитель 9, $N=704+10x$ — перебором находится единственный подходящий $x$.
3. Модульное сведение для блока «*». Блок длины $k$ обозначают переменной $X$ ($0\le X<10^k$), а число записывают как $N=A+X\cdot10^p+B$. Условие делимости превращается в сравнение $X\cdot10^p\equiv-(A+B)\pmod m$, которое решают через обратный элемент, если $\gcd(10^p,m)=1$.
4. Ограничение длины по условию. Если сказано «не превышает $10^k$», сначала находят все допустимые длины итогового числа при разных длинах «*» — обычно это 1–3 варианта, что резко сокращает объём вычислений.
5. Признаки делимости как фильтр. Если делитель раскладывается на удобные множители (3, 9, 11), иногда быстрее сначала проверить простые признаки, чтобы отсеять часть вариантов до модульных вычислений.

Алгоритм решения по шагам

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

Разбор примеров

Пример 1. Маска «12345?7?8», граница $10^9$, делитель 23. Маска без «*», длина числа фиксирована — 9 цифр. Пусть $A$ — цифра первого «?», $B$ — второго. Тогда $$N=123450708+1000A+10B.$$ Нужно $N\equiv0\pmod{23}$. Перебирая $A=0,\dots,9$ и решая для каждого $A$ уравнение относительно $B$ (так как $\gcd(10,23)=1$, решение единственно), находят шесть пар. Итоговые числа: $123450798,\,123451718,\,123453788,\,123454708,\,123456778,\,123459768$, а частные от деления на 23: $5367426,\,5367466,\,5367556,\,5367596,\,5367686,\,5367816$.

Пример 2. Маска «1?493*41», граница $10^{10}$, делитель 2023. Фиксированная часть — 7 символов, значит длина числа равна $7+k$. Поскольку $10^{10}$ — 11-значное число, а такая длина по этой маске недостижима, реально допустимы $k=0$ и $k=3$. При $k=0$: $N=1049341+100000A$, перебор остатков по модулю 2023 даёт единственное решение $A=3$, то есть $N=1349341$. При $k=3$ обозначим трёхзначный блок как $X$ ($0\le X\le999$): $$N=1049300041+100000000A+100X.$$ Переходя к остаткам по модулю 2023 и решая сравнение относительно $X$ для каждого $A=0,\dots,9$, находят допустимые (в диапазоне $0$–$999$) решения только при $A=2,5,8$, что даёт числа $1249338041,\,1549348941,\,1849359841$. Итоговый ответ по возрастанию: $1349341,\,1249338041,\,1549348941,\,1849359841$.

Пример 3. Маска «12*63?5?», граница $10^9$, делитель 3123. Фиксированная часть — 7 символов, длина числа $7+k$. Проверяем $k=0,1,2$. При $k=0$ (длина 7): $N=1263050+100C+D$, максимум $1263959$ — кратных 3123 в этом узком диапазоне нет, решений нет. При $k=1$ (длина 8), блок — одна цифра $x_1$: $N=12063050+100000x_1+100C+D$; перебор остатков даёт единственное решение $x_1=3,\,C=9,\,D=7$, то есть $N=12363957$. При $k=2$ (длина 9), блок — двузначное число $X$ ($0\le X\le99$): $N=120063050+100000X+100C+D$; решая сравнение по модулю 3123 для допустимых $X$, находят четыре решения: $120663351,\,120963159,\,124763850,\,125063658$. Итоговый ответ: $12363957,\,120663351,\,120963159,\,124763850,\,125063658$.

Типичные ошибки и ловушки

• Забыть, что «*» может задавать пустую последовательность — пропускается вариант минимальной длины числа.
• Неверно определить степень десяти для блока «*» из-за ошибки в подсчёте позиций фиксированных символов справа от блока.
• Не учесть ограничение сверху и рассмотреть длины числа, которые заведомо дают числа больше границы.
• Арифметическая ошибка при вычислении $10^n\bmod m$ — степени лучше считать пошагово, беря остаток на каждом шаге.
• Забыть про возможные нули внутри блока «*», если он стоит не в самом начале числа — такие варианты нужно учитывать.
• Ограничить перебор блока «*» диапазоном $0$–$10^{k-1}-1$ вместо $0$–$10^k-1$, случайно исключив числа с нулём в начале блока.
• Ошибка при подсчёте частного во второй колонке ответа — стоит проверять деление в столбик или обратным умножением.
• Выписать числа не по возрастанию или продублировать варианты из разных допустимых длин.

Как готовиться

Регулярно тренируйтесь раскладывать числа по разрядам и переводить условие маски в алгебраическое выражение — без этого навыка невозможно двигаться дальше. Отдельно отработайте технику быстрого вычисления остатков: умение находить $10^n\bmod m$ последовательным умножением с взятием остатка на каждом шаге экономит время и снижает число ошибок. Разберите расширенный алгоритм Евклида для поиска обратного элемента по модулю — он нужен, когда неизвестная связана с делителем множителем, взаимно простым с модулем.

Прорешайте не менее 10–15 задач с разными масками и делителями, обращая внимание на то, как меняется структура решения в зависимости от количества и расположения блоков «*». Для самопроверки в процессе подготовки полезно перебрать варианты вручную по алгоритму, а затем свериться прямым перебором меньшего диапазона — это помогает понять, на каком шаге чаще возникает ошибка: в разложении по разрядам, в переборе остатков или в границах диапазона.

Наконец, отработайте оформление ответа: числа строго по возрастанию, без пропусков и дублей, при необходимости — с частным от деления. Перед сдачей проверяйте, что учтён случай пустой подстановки «*» и что для каждой допустимой длины числа рассмотрены все её варианты.