SP279 INUMBER - Interesting number 题解

题目链接：INUMBER - Interesting number

题意：

对于给定的数 $n$，求出能被 $n$ 整除的最小正整数，其位数之和为 $n$。

输入格式：

第一行，输入一个整数 $T$，是测试用例的数量。

接下来的 $T$ 行，每行输入一个整数 $n$ 。

输出格式：

共 $T$ 行，答案。

数据范围：

$1 \le T \le 50,~1 < n \le 10^3$ 。

这个题貌似是05年的题，比 cxy 还大。 （但是 cxy 是萌妹子/oh）

看上去就是个搜索题。考虑 bfs 。记状态 $(x,y)$ 表示当前位数的和为 $x$ ，实际数$\bmod n$ 的值为 $y$ 。

初始状态 $(0,0)$ ，我们需要的是 $(n,0)$ 。其实还是蛮套路的，主要考察的就是模 $n$ 这个优化。

时间复杂度 $\mathcal{O}(n^2)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e3 + 55))
#define Fi first
#define Se second

char obuf[N];
int tim(0), vis[N][N];
pair<pii,int> pre[N][N]; queue<pii> q;
void solve()
{
    int n,x(-1),y(-1); cin >> n; ++tim; while(!q.empty()) q.pop();
    for(q.emplace(0,0); !q.empty(); )
    {
        x = q.front().Fi, y = q.front().Se; q.pop();
        if(x == n && y == 0) break;
        for(int i = (x ? 0 : 1); i <= 9; i++)
        {
            int tx = x + i, ty = (y * 10 + i) % n;
            if(tx > n || vis[tx][ty] == tim) continue;
            vis[tx][ty] = tim; pre[tx][ty] = {make_pair(x,y), i};
            q.emplace(tx,ty);
        }
    }
    int O = 1015; x = n; y = 0;
    while(x || y)
    {
        obuf[O--] = '0' + pre[x][y].Se;
        tie(x,y) = pre[x][y].Fi;
    }
    cout << obuf + O + 1 << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; cin >> Q; while(Q--) solve();
    return 0;
}

---

参考文献：

[1] https://stackoverflow.com/questions/32426222/spoj-inumber-cant-seem-to-develop-a-solution-within-the-time-limit

[2] https://github.com/gcdart/PC-solutions/blob/master/Spoj/INUMBER.cpp