AT3621 [ARC084B] Small Multiple
AtCoder: D - Small Multiple
给定一个整数 $K$ .求一个 $K$ 的整数倍 $SUM$ ,使得 $SUM$ 的数位累加和最小。
直接暴力的复杂度是不可接受的或者说答案的正确性是不能保证的，而直接暴力的方法是枚举 $k$ 的倍数，更新最小数位累加和。我们是否能直接奔着答案去，直接找到最小的数位累加和。 $sum$ 需要是 $k$ 的倍数，即 $sum \mod k = 0$ ，我们考虑同余最短路。对于一个数 $1$ ，我们如何让它成为一个数 $sum$ ，只需要两种操作，将其加 $1$，或将其乘 $10$ ，这能保证能成为任何一个数，而前者操作会使数位累加和增加 $1$ ，而不变。这样的话，研究大于 $k$ 的数是没有意义的，因为只有这两种操作，它模 $k$ 并不影响答案。所以就有了建图思路：
- 对于 $i > 0 \wedge i < k$ ，
add(i, (i + 1) % k, 1) ，add(i, i * 10 % k, 0) ；
- 从 $1$ 做最短路，其中 $d[1] = 1$ ，$d[0]$ 即为答案。
查看代码
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
44
45
46
47
48
49
| #include <cstdio>
#include <queue>
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;
bool vis[N];
int k, d[N];
int idx, hd[N], nxt[M], edg[M], wt[M];
void add(int a, int b, int c)
{
nxt[++idx] = hd[a];
hd[a] = idx;
edg[idx] = b;
wt[idx] = c;
}
int main()
{
scanf("%d", &k);
for (int i = 0; i < k; i++)
hd[i] = -1;
for (int i = 1; i < k; i++)
{
add(i, (i + 1) % k, 1);
add(i, i * 10 % k, 0);
}
for (int i = 0; i < k; i++)
d[i] = k;
d[1] = 1;
queue<int> q;
q.push(1);
vis[1] = true;
while (!q.empty())
{
int t = q.front();
q.pop();
vis[t] = false;
for (int i = hd[t]; ~i; i = nxt[i])
if (d[t] + wt[i] < d[edg[i]])
{
d[edg[i]] = d[t] + wt[i];
if (!vis[edg[i]])
{
q.push(edg[i]);
vis[edg[i]] = true;
}
}
}
printf("%d", d[0]);
return 0;
}
|