Define \(\text{d}[x][c]\) as the minimum number of digits of an integer that is congruent to \(x\) modulo \(X\), and a digit greater than or equal to \(c\) can be appended. This dynamic programming (DP) table can be filled in \(O(N\sigma^2)\) time, where \(\sigma=10\), by a Breadth-First Search (BFS) with the transitions \(\text{d}[(10x+c') \bmod N][c'] \leftarrow \text{d}[x][c]+1\) for \(c'=c,c+1,\ldots,9\). (By inspecting in ascending order of \(c'\) and break-ing once reaching an already-searched DP table, it can be easily improved to \(O(N\sigma)\) time.

Consider reconstructing the answer from this DP table. In addition to this table, maintain another two-dimensional array to store, for each element in the DP table, the origin of the transition into that element. Moreover, by performing BFS in ascending order of digits, the minimum value can be obtained by backtracking once you reach a DP-table element with \(x=0\). For more details, please refer to the sample code. (In this code, the two-dimensional array \(\text{d}[x][c]\) is represented as a one-dimensional array \(\text{d}[10\times x+c]\) for speedup.)

Sample code (Python 3)

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)

In fact, the implementation above uses the values stored in \(\text{d}\) only to check if it equals \(\text{INF}\), which happens if and only if \(\text{to}\) contains \(-1\). Thus, the problem can be solved by not explicitly constructing \(\text{d}\) and just maintaining \(\text{to}\).

Sample code (Python 3)

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)