题解 | #克苏鲁的规则#

克苏鲁的规则:前言

这题蛮有意思的。

听同学说用bfs做的，然后写了bfs挂了。

然后看他们代码，嚯嚯，取模了，然后他们解释下懂了。

题解

part 1

我们称各位数之和叫 $cnt$ ，数叫做 $num$ 。

首先呢，这个思想是从 $cnt = 1$ 开始广搜，对于每个 $cnt$ 它有多个 $num$ ，

比如对于 $1$ ，它可以是 $10$ , $100$ , $1000$ , $1000$ $...$

那到什么时候为止呢？

或许你会想，这个数它不能超过 $long$ $long$ 吧。。也许可作为限制条件。

那么接着，你就想怎么广搜，对于每个 $num$ ，你有两种选择，要么乘以 $10$ ，要么给它加上 $1$ ，其中注意到乘法是不影响 $cnt$ 的。

这意味着， $num$ 在加上 $1$ 后，可转移的新状态为 $((num$ + $1)*10^?,cnt$ + $1)$ ，把它们加入队列呗。

最后只要判断每次的num是否能整除 $n$ 就行了。

遗憾的是这样会 $T$ 。

part 2

不难注意到，每次的 $num$ 若能整除 $n$ 是就好了。进而 $num$ 的模数 $k$ 要是能整除 $n$ 就好了。再进而要是我知道怎么操作会使 $k$ 能整除 $n$ ，并且要是这样对 $num$ 搞，也 $cnt$ 相同就好了。（嘿嘿，就是贪它一手。）

结果一想发现什么呢？我要是对 $num$ 加 $1$ ，相当于加在模数 $k$ 上,我要是对 $num$ 乘 $10$ ， $num$ 中一部分能整除的数自然乘后还是乘除的，而不能整除的模数 $k$ 会受到影响。

哎，这不就意味着，直接对 $k$ 进行 $bfs$ 与对 $num$ 是等价的。

哦，那么这个时候乘多少个 $10$ 的问题就看什么时候算的 $k$ 见过了，就不乘了。加个记忆化，要是这个 $k$ 我见过，就不扩展了， $break$ 出去。因为之前就扩展过了。

Code

#include<bits/stdc++.h>
#define int long long
#define sec second
#define fst first
#define pii pair<int,int>
using namespace std;
queue<pii> q;

signed main(){
    // freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);
    int n;cin >> n;
    map<int,int> v;
    int t=1;
    while(!v[t]) v[t]++,q.push({ t,1 }),t=(t * 10) % n;
    while(q.size()){
        int num=q.front().fst,cnt=q.front().sec;
        if(num % n == 0){
            cout << cnt << endl;
            break;
        }
        num=(num + 1) * 10 % n;
        while(!v[num]) v[num]++,q.push({ num,cnt + 1 }),num=(num * 10) % n;
        q.pop();
    }
    return 0;
}