409选拔赛补题

Problem A - Find a Number

题目描述

给定两个正整数 $d$ 和 $s$，求一个能被 $d$ 整除，并且数位之和等于 $s$ 的最小正整数 $n$。

输入

第一行包含两个正整数 $d$ 和 $s$，满足 $1 \le d \le 500$，$1 \le s \le 5000$。

输出

如果存在答案，输出满足条件的最小正整数；否则输出 $-1$。

分析

可以把状态设计为：

$$(\text{当前模数},\text{当前数位和})$$

从一个状态后面追加一位数字 $x$ 后，新模数会变为：

$$(mod\times 10+x)\bmod d$$

数位和会增加 $x$。因此可以在状态图上跑 BFS。由于 BFS 按位数从小到大扩展，并且每次按数字从小到大转移，所以第一次到达状态 $(0,s)$ 时得到的就是最小答案。

同时记录每个状态的前驱和追加的数字，最后从 $(0,s)$ 倒推即可还原答案。

代码

queue> q;
bitset st[N][M];
int s, d;
struct node
{
    short x, y, z;
} path[N][M];
stack stk;
void solve()
{
    cin >> s >> d;
    st[0][0] = 1;
    q.push({0, 0});
    path[0][0] = {-1, -1, -1};
    while (q.size())
    {
        auto [mod, sum] = q.front();
        q.pop();
        for (int i = 0; i <= 9; i++)
        {
            int ver = (mod * 10 + i) % s, su = sum + i;
            if (su <= d && st[ver][su] == 0)
                q.push({ver, su}), st[ver][su] = 1, path[ver][su] = {mod, sum, i};
        }
    }
    if (st[0][d] == 0)
    {
        cout << -1 << "\n";
        return;
    }
    s = 0;
    while (path[s][d].x != -1)
    {
        auto [x, y, z] = path[s][d];
        stk.push(z);
        s = x, d = y;
    }
    while (stk.size())
    {
        cout << stk.top();
        stk.pop();
    }
}