\(\text{d}[x][c]\) を「\(N\) で割ったあまりが \(x\) となり、末尾につけられる整数が \(c\) 以上であるような良い整数の 桁数 の最小値」と定義します。この動的計画法は \(c'=c,c+1,\ldots,9\) に対し \(\text{d}[(10x+c') \bmod N][c'] \leftarrow \text{d}[x][c]+1\) という遷移を行う幅優先探索によって \(\sigma=10\) として \(O(N\sigma^2)\) 時間で計算することができます（ \(c'\) を昇順に見ていき、既に探索済みの DP テーブルに到達した場合に break することで \(O(N\sigma)\) 時間に簡単に改善できます）。

この DP テーブルから答えを復元することを考えます。この DP テーブルの他に、各 DP テーブルがどこから遷移してきたかを持つ別の二次元配列を用意します。さらに、幅優先探索を桁の昇順に行うことで、 \(x=0\) となる DP テーブルに到達した瞬間に逆順に復元していくことで最小値を得ることができます。詳しくは実装例を参考にしてください。（以下の実装例では高速化のために \(2\) 次元配列 \(\text{d}[x][c]\) を \(1\) 次元配列 \(\text{d}[10\times x+c]\) で表現しています。）

実装例(Python3)

from collections import deque

n = int(input())
INF = 10**9
d = [INF] * (10 * n)
to = [-1] * (10 * n)
d[0] = 0
q = deque([0])
while q:
    idx = q.popleft()
    c, x = idx % 10, idx // 10
    for cc in range(max(1, c), 10):
        xx = (10 * x + cc) % n
        idx2 = 10 * xx + cc
        if d[idx2] != INF:
            break
        d[idx2] = d[idx] + 1
        q.append(idx2)
        to[idx2] = idx
        if xx == 0:
            ans = []
            cur = idx2
            while cur != 0:
                ans.append(str(cur % 10))
                cur = to[cur]
            print("".join(ans[::-1]))
            exit()
print(-1)

また、上の実装では \(\text{d}\) は中に入った数字が \(\text{INF}\) と同じかどうかの確認にしか使っておらず、それは \(\text{to}\) の中が \(-1\) であることと同値なので \(\text{d}\) を作らずに \(\text{to}\) のみを構築する解法でも正答することができます。

実装例(Python3)

from collections import deque

n = int(input())
INF = 10**9
to = [-1] * (10 * n)
q = deque([0])
while q:
    idx = q.popleft()
    c, x = idx % 10, idx // 10
    for cc in range(max(1, c), 10):
        xx = (10 * x + cc) % n
        idx2 = 10 * xx + cc
        if to[idx2] != -1:
            break
        q.append(idx2)
        to[idx2] = idx
        if xx == 0:
            ans = []
            cur = idx2
            while cur != 0:
                ans.append(str(cur % 10))
                cur = to[cur]
            print("".join(ans[::-1]))
            exit()
print(-1)