arc 084D-Small Multiple[最短路]

Problem Statement

Find the smallest possible sum of the digits in the decimal notation of a positive multiple of $K$.

Constraints

  • $2≤K≤10^5$
  • $K$ is an integer.

Input

Input is given from Standard Input in the following format:

1
K

Output

Print the smallest possible sum of the digits in the decimal notation of a positive multiple of $K$.

Sample Input 1

1
6

Sample Output 1

1
3

$12=6×2$ yields the smallest sum.

Sample Input 2

1
41

Sample Output 2

1
5

$11111=41×271$ yields the smallest sum.

Solution

当时是lzh教我做的来着.

点i表示%k=i的点,这道题相当于求0~0的最短路(显然不可以这么写)。

于是我们就可以把 1 ~ 9 都入队。

加边:枚余数,作为左端点,后面加一个数$x$($0 \le x \le 9$ ),边权为 $x$ ,右端点为 $(余数×10+x)%k$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
int dis[maxn],k,vis[maxn];
int to[maxn*10],w[maxn*10],ne[maxn*10];
int po[maxn],id;
queue<int> q;
inline void add(int x,int y,int z)
{
to[++id]=y;w[id]=z;ne[id]=po[x];po[x]=id;
}
int main()
{
memset(dis,0x3f3f3f3f,sizeof(dis));
cin>>k;
for (int i=0;i<k;i++)//枚余数
for (int j=0;j<=9;j++)//往后添一个数
add(i,(i*10+j)%k,j);
for (int i=1;i<=9;i++)
{
q.push(i);dis[i]=i;vis[i]=1;
}
while (!q.empty())
{
int u,v;
u=q.front();q.pop();vis[u]=0;
for (int i=po[u];i;i=ne[i])
{
v=to[i];
if (dis[u]+w[i]<dis[v])
{
dis[v]=dis[u]+w[i];
if (!vis[v])
{
q.push(v);
vis[v]=1;
}
}
}
}
printf("%d\n",dis[0]);
return 0;
}