给定一个整数 。求一个 的正整数倍 ,使得 的数位累加和最小。
。
考虑一位一位填,,所以可以在 的意义下运算,从 向 ()连权值为 的有向边。答案即为 的最短路长度 。
注意到这是最短路,所以实际上从 向 连权值为 的有向边,向 连权值为 的有向边也可以,因为最短路时个位进位一定不优,但是最长路就不能这样建边。这样建边的好处是可以 01 bfs 求解。
注意 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;
}