令状态$f(i, j)$表示模$d$为$i$，和为$j$时的最小数
可以通过$bfs$来转移
然而就没了...
复杂度$O(10ds)$
#include <queue> #include <vector> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> namespace remoon { #define ri register int #define ll long long #define pii pair<int, int> #define mp make_pair #define pb push_back #define fi first #define se second #define tpr template <typename ra> #define rep(iu, st, ed) for(ri iu = st; iu <= ed; iu ++) #define drep(iu, ed, st) for(ri iu = ed; iu >= st; iu --) #define gc getchar inline int read() { int p = 0, w = 1; char c = gc(); while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); } while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc(); return p * w; } } using namespace std; using namespace remoon; #define sid 525 #define pid 5205 int d, s; struct node { int d, s, di; node() {} node(int a, int b, int c) : d(a), s(b), di(c) {} }; queue <pii> q; bool vis[sid][pid]; node pre[sid][pid]; void bfs() { vis[0][0] = 1; q.push(mp(0, 0)); while(!q.empty()) { pii p = q.front(); q.pop(); rep(i, 0, 9) { int nd = (p.fi * 10 + i) % d; int ns = p.se + i; if(ns > s) break; if(!vis[nd][ns]) { vis[nd][ns] = 1; q.push(mp(nd, ns)); pre[nd][ns] = node(p.fi, p.se, i + '0'); } } } } inline void dfs(int nd, int ns) { if(pre[nd][ns].di != 0) dfs(pre[nd][ns].d, pre[nd][ns].s); if(pre[nd][ns].di != 0) printf("%c", pre[nd][ns].di); } int main() { d = read(); s = read(); bfs(); if(!vis[0][s]) puts("-1"); else dfs(0, s); return 0; }