题意

题目链接: 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$ 的最短路就是所求答案

Code

Submission #16551083: https://atcoder.jp/contests/arc084/submissions/16551083

考虑边权 $\in \{0,1\}$，所以直接 bfs 即可

#include <cstdio>

#include <queue>

const int N = 1e5 + 1e4;

int k;
bool vis[N];

struct node { int cur, val; };

int main() {
    scanf( "%d", &k );
    std::deque<node> q;
    q.push_front( (node){ 1, 1 } );
    while( !q.empty() ) {
        node top = q.front(); q.pop_front();
        if( vis[ top.cur ] )
            continue;
        vis[ top.cur ] = true;
        if( top.cur == 0 ) {
            printf( "%d\n", top.val );
            return  0;
        }
        q.push_front((node){ ( top.cur * 10 ) % k, top.val });
        q.push_back((node){ ( top.cur + 1 ) % k, top.val + 1 });
    }
}