AT_arc084_b [ABC077D] Small Multiple 做题记录

给定一个整数 $K$。求一个 $K$ 的正整数倍 $S$，使得 $S$ 的数位累加和最小。

$2 \le K \le {10}^5$。

考虑一位一位填，$\overline{AB}=A\times 10+B$，所以可以在 $\operatorname{mod} k$ 的意义下运算，从 $x$ 向 $10x+b\operatorname{mod} k$（$0\le b\le 9$）连权值为 $b$ 的有向边。答案即为 $1\to 0$ 的最短路长度 $+1$。

注意到这是最短路，所以实际上从 $x$ 向 $10x$ 连权值为 $0$ 的有向边，向 $x+1$ 连权值为 $1$ 的有向边也可以，因为最短路时个位进位一定不优，但是最长路就不能这样建边。这样建边的好处是可以 01 bfs $O(n)$ 求解。

注意 01 bfs 每个点的最短路会更新至多两次。

代码如下：

// Problem: [ABC077D] Small Multiple
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_arc084_b
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstdio>
#include <deque>
#include <cstring>

using namespace std;

const int S=200005;

int n,dis[S];

int main()
{
	scanf("%d",&n);
	deque<int> q;
	dis[1]=1;
	q.push_back(1);
	while(!q.empty())
	{
		int u=q.front();
		q.pop_front();
		int v=u*10%n;
		if(dis[v]==0||dis[u]<dis[v])
		{
			dis[v]=dis[u];
			q.push_front(v);
		}
		v=(u+1)%n;
		if(dis[v]==0||dis[u]+1<dis[v])
		{
			dis[v]=dis[u]+1;
			q.push_back(v);
		}
	}
	printf("%d\n",dis[0]);
	return 0;
}