给定一个自然数N，找出一个M，使得M > 0且M是N的倍数，并且M的10进制表示只包含0或1。求最小的M。
例如：N = 4，M = 100。
Input
输入1个数N。(1 <= N <= 10^6)
Output
输出符合条件的最小的M。
Input示例
4
Output示例
100
对于m每一位上的数要么是0 要么是1，那就可以枚举每一位上的值，又得到的m最小，那么可以bfs解决，但是这题的n比较大，普通的bfs不行，会爆__int64 所以需要优化，
可以定义一个数组，标记每次出现的余数，因为同于定理，如果当前的余数之前出现过那么久没有必要再对当前的数进行运算。又m最后会很大，所以需要存储当前满足条件的路径和值。
#include<map> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define INF 1000000001 #define ll __int64 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; const int MAXN = 1000010; struct node { int flag; int val; int fa; }a[MAXN]; int vis[MAXN]; int cnt; int n,ans; void bfs() { queue<int>q; cnt = 1; a[0].fa = -1; a[0].flag = 1; a[0].val = 1; vis[1] = 1; q.push(0); while(!q.empty()){ int t = q.front(); q.pop(); if(a[t].val == 0){ ans = t; return; } a[cnt].flag = 0; a[cnt].val = (a[t].val * 10) % n; a[cnt].fa = t; if(!vis[a[cnt].val]){ vis[a[cnt].val] = 1; q.push(cnt); cnt++; } a[cnt].flag = 1; a[cnt].val = (a[t].val * 10 + 1) % n; a[cnt].fa = t; if(!vis[a[cnt].val]){ vis[a[cnt].val] = 1; q.push(cnt); cnt++; } } } void find(int p) { if(p == -1)return; find(a[p].fa); printf("%d",a[p].flag); } int main() { while(cin >>n){ if(n == 1){ cout<<1<<endl; continue; } memset(vis,0,sizeof(vis)); bfs(); find(ans); cout<<endl; } }