A - Find a Number CodeForces - 1070A -记忆化广搜-同余定理_codeforces 1070a find a number(bfs)-CSDN博客
这个大佬的博客代码写的非常好看。
————
（其实第二个样例32位的数long long存不下，就知道这道题不是寻常做法，可惜没有想法。。）
思路：
每一位有0~9这些情况，对于这些情况的每一种，下一位也有0~9种。
这个可以bfs遍历。
遍历的时候这些数加起来不就是数位和嘛。
变大的过程中，可能数位和不够，可能余数不为0，所以要接着变大。
其实在所有满足的数位和的数里看是否有个数是d的倍数即可。
（变大的过程中会出现余数相同，数位和相同的情况，因为他们接下来的变化相同，所以只算一次就够了，而且先来的小，我们要的就是最小的。）
数组解释：
每次我们对旧数乘以10 ，然后个位加新数，所以是倒着来的。
最后要正着输出，所以我们顺便记录每次加的新数 i 是多少（pre记录前一个，id当前数字）。
（注意，最后要的余数为0）
typedef pair<int, int> PII;
int d, s;
int vis[501][5001];
PII pre[501][5001];
int id[501][5001];
void bfs()
{
queue<PII>q;
q.push({ 0,0 });
vis[0][0] = 1;
while (q.size())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 10; i++)
{
int tx = (x * 10 + i) % d;//每一个数都遍历了
int ty = y + i;//每次加i，所以位数和加i
if (vis[tx][ty] || ty > s)continue;
vis[tx][ty] = 1;
q.push({ tx,ty });
pre[tx][ty] = { x,y };
id[tx][ty] = i;//新增位
}
}
if (vis[0][s] != 1)
{
cout << -1 << endl;
return;
}
stack<int>ans;
d = 0;//*最后一位余数为0
while (d!=0||s!=0)
{
ans.push(id[d][s]);
int cd = d, cs = s;
d = pre[cd][cs].first;
s = pre[cd][cs].second;
}
while (ans.size())
{
cout << ans.top();
ans.pop();
}
}
void solve()
{
cin >> d >> s;
bfs();
}
signed main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int t = 1;
//cin >> t;
while (t--)
{
solve();
}
return 0;
}
