题意

题目链接: https://atcoder.jp/contests/arc084/tasks/arc084_b

要求 $x = ak(a \in N)$，定义 $f(x)$ 为 $x$ 在十进制下每一位数字的和

思路

一开始肯定想的是大力枚举，但是很快就可以发现大力枚举可以被卡掉，因为另一个数字可以非常大

然后就考虑缩小另一个数字的范围

一开始的思路顺着质因数分解走的，但是想了半天没有想出来

考后发现顺着质因数的过于复杂，我们可以直接考虑 $x \bmod k$ 意义下的情况

从 $x$ 到 $x + 1$，答案显然增加 1

但是如果 x 一直加 1 会加到 10 ，这个情况答案在事实上没有增加 1

我们可以发现只有其在某一步变成 10 倍才会发生这种事件，那么再加一条边

从 $x$ 到 $10x$，答案不增加

这样就构成了一条图，从 $0$ 到 $1$ 的最短路就是所求答案

Continue reading “AtCoder Regular Contest 084 D Small Multiple”