ABC077 D - Small Multiple

問題
提出コード
桁和関連の問題は本当に解ける気がしないです…方針が立ちません。解説を読んでもわからないので、数日寝かせていました。

解法

について、基本的には1を足すと桁和が1増加し(例外があります)、10倍すると桁和は据え置きです。
ということで、この2種類をそれぞれコスト1、コスト0の辺とみなして1からグラフを作成していくと、最終的に1からの倍数への最短経路+1の最小値が答えとなります。
例外として、等のような、1追加すると繰り上がりが発生して桁和が減少するパターンがありますが、これが起きるのはすべて1の位が9の場合であり、1を足すと必ず10の倍数になります。結局、の1の位が9の場合は、を10倍したパターンが最短経路になっているため、このようなの場合に1を足す操作はあまり気にしなくてよいことになります。
ということで、あとはグラフ作成と最短経路を求めるだけなのですが、ここで
～のグラフの辺の張り方は、～の辺の張り方と一致しているため、で割った余りについてのみ考えてあげれば、個の頂点のみを用いたグラフで答えを求めることができます。
ということで、ある数に対して、10倍してあげる操作をコスト0、1追加する操作をコスト1として、頂点1から頂点0への最短経路を求めてあげれば、それに1追加したものが最終的な答えになります。