Коротко — идеи, алгоритмы и важные тонкости.
Основные наблюдения
- Сумма цифр связана с остатком по 9: $n\equiv s(\mathrm{mod}9)$.\) Следовательно необходимое условие существования решения: $s\equiv 0(\mathrm{mod}\gcd (m,9))$.\)
- Минимальное возможное количество цифр (если $s>0$) —
$L_{\min }=\lceil s/9\rceil$.\) (для $s=0$ единственная подходящая цифра — $0$.)
- При прочих равных меньшее количество цифр даёт строго меньшее по значению число, а при фиксированной длине минимальное по значению число получают, выбирая слева как можно меньшие цифры, оставляя возможность распределить остаток суммы по справа.
Алгоритмы (по возрастанию универсальности / стоимости)
1) BFS / динамика по состоянию (остаток, оставшаяся сумма) — прямой точный метод
- Состояния: $(r,t)$ — текущий остаток $\mathrm{mod}m$ и оставшаяся сумма цифр $t$.
- Переходы: добавить справа цифру $d\in \{\mathrm{0..9}\}$ (первый шаг — $d\in \{\mathrm{1..9}\}$ если число нельзя начинать с нуля), новый остаток $r^{\prime }=(10r+d)\mathrm{mod}m$, уменьшить $t$ на $d$.
- Запускают BFS от $(0,s)$ в глубину «количество добавленных цифр»; при достижении $(0,0)$ первый найденный путь даёт число с минимальной длиной, а порядок перебора цифр (0..9) даёт лексикографически (то есть численно) минимальное среди тех же длин.
- Сложность/память: порядок $O(m\cdot s)$ состояний и $O(10\cdot m\cdot s)$ переходов — пригодно для умеренных $m,s$ (тысячи... десятки тысяч с оптимизациями).
2) Фиксация длины + жадная конструция с предвычислением достижимых остатков (рекомендуемый для больших m, средних s)
- Перебираем длину $L$ от $L_{\min }$ вверх. Для данного $L$ хотим проверить, существует ли число длины $L$ с суммой $s$ и остатком $0$.
- Предвычисляем DP для «остатков, которые можно получить за r оставшихся позиций при сумме t» как битсеты по модулю $m$. Рекуррент: для одной позиции набор достижимых остатков — сдвиги битсета предыдущего уровня по значениям $d$.
- Затем по позициям строим число жадно: на i-й позиции берем минимальную допустимую цифру $d$ (для i=1 — не ноль), такую что оставшаяся сумма распределима и остаток 0 достижим в конце (см. предвычисленные битсеты).
- Если ни для одного $L$ не нашлось — увеличить $L$.
- Оптимизация: хранить битсеты длины $m$ и выполнять добавления/сдвиги за $\lceil m/word\rceil$ слов; сложность примерно $O(L\cdot s\cdot m/word)$. Работает для $m$ до десятков тысяч при аккуратной реализации.
3) Конструктивные численно-теоретические методы для очень больших $s$ - Если $s$ большой, часто $s=9q+r$ и решение «состоит» из большого количества девяток и небольшого префикса. Можно искать число в виде префикс P и q блоков по t подряд 9 (или вообще q девяток подряд): блочное представление позволяет оперировать формулой для числа из $t$ девяток — это $999\dots 9_{(t)}=10^t-1$.
- Решение сводится к поиску префикса $A$ и количества блоков/позиции девяток, дающих нужный остаток:
решать по модулю $m$ сравнения типа $(A\cdot 10^k+(10^k-1))\equiv 0(\mathrm{mod}m)$.
- Применяют перебор небольшой длины префикса и/или применение циклов по остаткам $10^t\mathrm{mod}m$ (периодичность), чтобы быстро найти приемлемые $t$. Это даёт компактное представление большого числа без перебора всех состояний.
- Такой метод требует аккуратной схемы доказательства минимальности (обычно минимальная длина = $\lceil s/9\rceil$, поэтому можно ограничить поиски) и работы с остатками $10^k\mathrm{mod}m$ (быстрый экспоненциал по модулю, поиск по циклу остатков).
Важные тонкости и практические замечания
- Необходимое условие через 9: $s\equiv 0(\mathrm{mod}\gcd (m,9))$ — если не выполняется, решений нет.
- Если $\gcd (10,m)>1$ (например $m$ чётно или делится на 5), умножение на 10 сужает множество достижимых остатков и может потребоваться увеличивать длину числа значительно — это влияет на достижимость конкретных остатков и на периодичность остатков $10^k\mathrm{mod}m$.
- Пограничные случаи: $s=0$ даёт единственное $n=0$; нельзя допускать ведущие нули при проверке длины.
- Выходной результат может иметь длину $\Theta (s/9)$. При очень больших $s$ хранить/печать число невозможно — возвращайте сжатое представление (количество девяток, префикс).
- Асимптотика методов: прямой BFS/DP $O(ms)$ — простой, но быстро не масштабирует; битсет-динамика + жадная сборка — хороший компромисс; численно-теоретические трюки нужны при экстремально больших $s$ и/или $m$.
Рекомендация для реализации
- Для практических ограничений (например $m,s\lesssim 10^4$) — реализуйте BFS по $(r,t)$ или DP с восстановлением пути.
- Для $m$ до десятков тысяч и $s$ до десятков тысяч — используйте DP с битсетами по остаткам и жадную конструцию по длине.
- Для $s$ очень большого — сначала свести задачу к форме «префикс + блоки девяток», перебирая короткие префиксы и пользуясь свойствами $10^k\mathrm{mod}m$.
Если нужно, могу привести код-скелет (BFS или битсетовую реализацию) для конкретных ограничений $m$ и $s$.