Шешімі: Маска числа и делимость
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: символ «?» означает ровно одну произвольную цифру; символ «*» означает любую последовательность цифр произвольной длины, в том числе пустую. Например, маске 123*4?5 соответствуют числа 123405 и 12300405. Среди натуральных чисел, не превышающих $10^{10}$, найдите все числа, соответствующие маске 3?12?14*5, делящиеся на 1917 без остатка.
Шешім по шагам
3 қадамФиксированная часть маски имеет вид $3a12b14$, где $a$ и $b$ — цифры. Символ «*» может задавать от 0 до 3 цифр, поскольку число не превышает $10^{10}$.
$$N=(3012014+100000a+1000b)\cdot10^k+s$$Перебираем $a,b\in\{0,1,\ldots,9\}$, длину окончания $k\in\{0,1,2,3\}$ и все значения $s$ от $0$ до $10^k-1$. Оставляем только числа, для которых $N\bmod1917=0$.
Для ускорения перебора остаток окончания определяется однозначно: $s\equiv-(3012014+100000a+1000b)\cdot10^k\pmod{1917}$. Если полученное $s$ не меньше $10^k$, такое сочетание не подходит.
Перебрать все значения a, b, k и s по указанной схеме; подходящие числа вывести по возрастанию вместе с частными от деления на 1917.
Бұл жауап талдау нәтижесінде алынды, бірақ банктің ресми кілтімен тексерілген жоқ — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Разрешают символу «*» төрт цифры, хотя тогда возможны числа больше $10^{10}$.
Не допускают пустую последовательность для символа «*».
Проверяют только делимость фиксированной части маски, не перебирая окончание.
Выводят числа не в порядке возрастания.