Loading... ## 题意 给定一个$K(1\le K \le 10^5)$，令$sum(x)$表示$x$数位和，求$\min\limits_{K\mid n}\{sum(n)\}$。 ## 分析 首先$K\mid n\Leftrightarrow n \mod K=0$，那么我们可以建图，对于每个点（数字$x$）标记点权$a(x)=x\mod K$，并且建立两种有向边： * 将$x$指向$x+1$，边权为$1$ * 将$x$指向$x*10$，边权为$0$ 那么我们所求的答案，就是图上到任意一个$a(x)=0$点的最短路。这个最短路是典型的**01bfs**求法。 由于加法和乘法都可以和取模交换顺序，所以这样建边从旧点可以直接得到新点的点权。而这样做的妙处在于点上不需要维护可能很大的数字，只需要维护余数即可。 ## 代码 ```cpp int k; deque<pii> dq; #define N 100005 bool vis[N]; int main() { cin >> k; dq.push_back(mp(1, 1)); while (true) { auto v = dq.front(); if (v.first == 0) { cout << v.second; return 0; } dq.pop_front(); if (vis[v.first]) continue; vis[v.first] = true; if (!vis[v.first * 10 % k]) dq.push_front(mp(v.first * 10 % k, v.second)); if (!vis[(v.first + 1) % k]) dq.push_back(mp((v.first + 1) % k, v.second + 1)); } return 0; } ``` 细节： 不能在入队的时候设vis标记为true，只能在被访问的时候设。因为有一种情况的点是要重复入队的： * 末位为$9$然后通过$+1$方式在队尾入队是不优的，要通过$*10$在队首入队的情况提前访问掉。 * 这个不优很好理解。通过个位数的9进位（1239->1240），达成原数字（1239）的时候已经在个位（9）浪费太多次数了，远不如$*10$进位（124->1240）更优。 * 而由于点上存的$a(x)$是已经模$k$之后的结果，所以难以判断末位$9$并防止入队。 ## 启发 * 在数位上操作的东西$\Longrightarrow$ **01bfs** * 整除$\Longrightarrow$ **同余最短路** © 允许规范转载 打赏 赞赏作者 赞 如果觉得我的文章对你有用，请随意赞赏