1. 题目

传送门=￣ω￣=

题意：给出一个正整数 $K(K \in [2, 10 ^ 5])$，求一个正整数 $X$使得 $X \equiv 0 \mod K$且 $X$的各个位的数字之和最小（比如 $123$的各个位的数字之和为 $1 + 2 + 3 = 6$）

输出 $X$各个位的数字之和。

可以证明这个答案是唯一的（这不是废话吗）

2. 题解

考场碰到这题直接暴力了，我 TCL

实际上我把这题写个题解只是觉得 01BFS 很妙 OvO…

首先可以在模 $K$意义下连边：

• $i$到 $i+1$连一条长度为 $1$的边（各个位数字之和 $+1$）
• $i$到 $i \times 10$连一条长度为 $0$的边（各个位置数字之和不变）

（注意 $i + 1$和 $i \times 10$都是要对 $K$取模的）

然后从 $1$为起点跑一遍单源最短路即可。

最后输出 $dis[0] + 1$

如果最短路用 DIJ 复杂度是 $O(k log _ 2 k)$的

但是如果用 01BFS 就能做到 $O(k)$！

01BFS 能在 $O(n + m)$的复杂度内解决边权为 $0$或 $1$的图上的单源最短路问题。

具体实现很简单：

搞个双端队列，每次取出队首元素，从它开始扩展，如果下一条边长度为 $0$，则把这条边对应的后继节点插入到队首，如果为 $1$则插入到队尾。

这样我们能保证每次队首取出来的元素的 $dis$值是队列中最小的，思想就是和 DIJ 一样的，但是它没有 $log _ 2$，多棒～

注意这个 BFS 和普通的有所不同，01BFS 的 $dis$是该点作为队首元素时确定的，而不是第一次作为后继节点时确定的

具体看代码吧，代码很简单的 OvO…

（对了，实际上不推荐使用 STL 的 deque，慢得一匹。。。双端队列你手写是最好的，反正空间复杂度不超过时间复杂度，实在不行写个循环队列就行了。。。）

（要是实在是懒的话可以用 STL 的 list 都比这个好。。。deque 比 list 多一个 []运算符随机访问，类似于 vector）

（被这玩意坑过）

代码：

#include <bits/stdc++.h>

#define NS (100005)

using namespace std;

int n, dis[NS];

deque<int> que;

bool book[NS];

int main(int argc, char const* argv[])
{
    freopen("num.in", "r", stdin), freopen("num.out", "w", stdout);
    scanf("%d", &n), memset(dis, 127, sizeof(dis));
    que.push_back(1), dis[1] = 1;
    while (!que.empty())
    {
        int F = que.front(); que.pop_front();
        if (book[F]) continue;
        book[F] = 1;
        if (dis[F * 10 % n] > dis[F])
            dis[F * 10 % n] = dis[F], que.push_front(F * 10 % n);
        if (dis[(F + 1) % n] > dis[F] + 1)
            dis[(F + 1) % n] = dis[F] + 1, que.push_back((F + 1) % n);
    }
    printf("%d\n", dis[0]);
    return 0;
}