题目:给定一个自然数N,找出一个M,使得M > 0且M是N的倍数,并且M的10进制表示只包含0或1。求最小的M。

例如:N = 4,M = 100。


题解:因为答案必须为十进制只包含01的数,所以我们只需要不断把当前数*10,和当前数*10+1放入队列即可。因为最终得到的结果可能会超出long long型,所以我们可以用字符串来存储,然后按照大数取模来计算余数即可。为什么要计算余数呢?因为如果一个数是N的倍数。那么余数必然为0,所以我们不断将他余N的余数倍增最后找到一个余数0即可。然后这里有一个很明显的剪枝,如果当前余数已经出现过了,那么就不需要把这个数再放入队列了。代码量很短,但是时间耗费貌似比较长,600MS了。。。)


代码:

#include <bits/stdc++.h>
using namespace std;
struct Node{
    string num;
    int rem;
    Node(string _num, int _rem){num=_num, rem=_rem;}
    Node(){}
};
int n;
const int maxn=1e6+5;
queue<Node> que;
bool vis[maxn];
int main()
{
    cin.sync_with_stdio(false);
    cin>>n;
    que.push(Node("1", 1%n));
    while(!que.empty()){
        Node now=que.front();
        que.pop();
        int mod=now.rem;
        if(mod==0){
            cout<<now.num<<endl;
            break;
        }
        else if(!vis[mod]){
            vis[mod]++;
            que.push(Node(now.num+'0', mod*10%n));
            que.push(Node(now.num+'1', (mod*10+1)%n));
        }
    }
    return 0;
}