Description
给定一个整数 \(K\) 。求一个 \(K\) 的正整数倍 \(S\)，使得 \(S\) 的数位累加和最小。
\(2\le K\le 10^5\)。
Solution
先不去考虑 \(K\) 的倍数这件事。思考如何快速得到一些数的数位累加和。
一个数的数位和，可以看成这个数在当前数位上加了几次。那么如果我们从 \(1\) 出发，那么就会有两条路：当前数位加一或者进入到下一个数位，其体现为 \(+1\) 和 \(\times 10\)。而 \(+1\) 会使数位和增加，但 \(\times 10\) 不会。
但怎么找到 \(K\) 的倍数呢？我们从余数的角度来考虑。那么 \(+1\) 和 \(\times 10\) 就相当于从一个余数连向另一个余数的边，\(+1\) 边权值为 \(1\)，\(\times 10\) 边权值为 \(0\)。最终答案就为 \(1\) 到 \(0\) 的最短路。
Code
#include<queue>
#include<cstdio>
#include<cstring>
#define N 100005
using namespace std;
int n,dis[N];
bool bj[N];
struct node {int x,dis;};
deque<node> q;
int main()
{
scanf("%d",&n);
memset(dis,0x3f3f3f3f,sizeof(dis));
q.push_back((node){1,1});dis[1]=1;
while (!q.empty())
{
int x=q.front().x,d=q.front().dis;q.pop_front();
if (dis[x]<d) continue;
if (bj[x]) continue;
bj[x]=true;
if (dis[(x+1)%n]>dis[x]+1)
{
dis[(x+1)%n]=dis[x]+1;
if (!bj[(x+1)%n]) q.push_back((node){(x+1)%n,dis[(x+1)%n]});
}
if (dis[x*10%n]>dis[x])
{
dis[x*10%n]=dis[x];
if (!bj[x*10%n]) q.push_front((node){x*10%n,dis[x*10%n]});
}
}
printf("%d\n",dis[0]);
return 0;
}