AT_arc084_b [ABC077D] Small Multiple 做题记录

给定一个整数 KK。求一个 KK 的正整数倍 SS,使得 SS 的数位累加和最小。

2K1052 \le K \le {10}^5

考虑一位一位填,AB=A×10+B\overline{AB}=A\times 10+B,所以可以在 modk\operatorname{mod} k 的意义下运算,从 xx10x+bmodk10x+b\operatorname{mod} k0b90\le b\le 9)连权值为 bb 的有向边。答案即为 101\to 0 的最短路长度 +1+1

注意到这是最短路,所以实际上从 xx10x10x 连权值为 00 的有向边,向 x+1x+1 连权值为 11 的有向边也可以,因为最短路时个位进位一定不优,但是最长路就不能这样建边。这样建边的好处是可以 01 bfs O(n)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;
}