初期状態から数字を一桁ずつ追加して任意の数値を構築するという操作を考えます。

この操作を \(K + 1\) 頂点の重み付き有向グラフでの遷移に当てはめます。

• 頂点 \(i (0 \le i \lt K)\) は \(i\bmod K\) である数が構築された状態
• 頂点 \(K\) は初期状態を表す

とします。

初期状態を特別扱いするのは\(0\bmod K\) と異なる頂点として扱いたいためです。

また、数字\(x\) を追加することを重み \(x\) の辺を追加することとして考えます。

こうすると頂点 \(K\) から頂点 \(0\) への最短経路が求める答えになります。

グラフの構築

まず、初期状態から数字を一つ加える操作を考えます。これは頂点 \(K\) から 頂点\(1, 2,3,4,5,6,7,8,9\) にそれぞれ重み \(1, 2,3,4,5,6,7,8,9\) で辺を追加するのに相当します。
\(K \lt 10\) のときは遷移先の頂点が \(\mod K\) になることに注意してください。

次に、構築済みの数値 \(i (0 \le i \lt K)\) からの遷移を構築します。できる操作は「\(10\)倍して数値 \(x\) を加える」です。
これは頂点 \(i (0 \le i \lt K)\) から頂点 \( 10 i + x (0 \le x \le 9)\) へ重み \(x\) の辺を追加するのに相当します。

これで、グラフの構築が完了したので Dijkstra 法で\(O(K \log K)\) で解くことができます。