题目描述

LCR和小A在玩这样一个游戏。LCR在纸上写了一个数字$n$，紧接着又在另一张纸上写了一个数字$1$，接下来小A可以在这个$1$的后面随意添加一些$0$或者$1$，从而得到一个新的数字，现在LCR希望小A得到的这个新的数字是$n$的倍数。由于小A很懒，所以他希望自己添加的$0$和$1$的个数的总和最小（这样他动笔次数就最少）。你需要帮助小A算出他最少需要在初始的$1$后面填加多少个数码才能使得这个新数字是$n$的倍数，如果无论添加多少个数码都不能是$n$的倍数，那么你需要输出$−1$。

【输入格式】

一行一个正整数$n$。

【输出格式】

共一行，一个数字表示小A最少需要添加多少个数码。

【输入输出样例#1】

输入#1

2

输出#1

1

【输入输出样例#2】

输入#2

6

输出#2

3

【输入输出样例#3】
输入#3

84447

输出#3

21

【说明提示】

你可以认为小A刚开始的数码是$x=1$，接下来他有两种变化数码的方式，要么把$x$变为$x×10+1$，要么把x变为$x×10$。
对于样例$2$，$1110$就是$6$的倍数，可以看作是在$1$的后面添了$3$个数码，可以证明，这就是添数码最少的方案。

【数据范围】

$2≤n≤2×10^5$
所有输入均为整数。

这道题是BFS(广搜)题，但是有一点难度，需要仔细想想。

• 先说第一种思路，就是普通广搜，每次值变化就乘$10$加$1$或者乘$10$，但是这样会超，可能存不下，会爆掉，并且数组也开不了那么大的数。

• 再说正解，由于要判断的是能不能整除，所以需要用到数学知识，
  直接看余数，根据同余定理直接对余数做执行操作，就可以拿到满分。

C++代码：

#include <iostream>
#include <cstring>
#include <queue>
#include <map>
using namespace std;
bool vis[200007];
int n;
struct node {
    int x, t;
};  
int bfs() {
    queue<node> q;
    q.push({1, 0});
    vis[1] = 1;
    while (q.size()) {
        node hd = q.front();
        q.pop();
        if (hd.x == 0) return hd.t;
        int p1 = (hd.x * 10) % n, p2 = (hd.x * 10 + 1) % n;
        if (!vis[p1]) {
            q.push({p1, hd.t + 1});
            vis[p1] = 1;
        } 
        if (!vis[p2]) {
            q.push({p2, hd.t + 1});
            vis[p2] = 1;
        } 
    }
    return -1;
}
int main() {
    cin >> n;
    cout << bfs();
    return 0;
}