【题意】给定一个自然数N，找出一个M，使得M > 0且M是N的倍数，并且M的10进制表示，是由0和1组成的。求最小的M。例如：N = 4，M = 100。
输入1个数N。(1 <= N <= 10^6)；
【分析】由于只有01组成，所以10^6就只有2^6的可能，似乎可以搜索？于是写了一发BFS，由于存在位数很大的答案，结果超时+爆内存。
其实可以用同余定理来剪枝，判断每个余数出现过就不需要搜下去了，然后最后输出答案只需要记录前驱即可。
【AC CODE】46ms
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 1e6+10;
struct NODE{
int val,m,fa;
}node[MAXN];
bool vis[MAXN];
int n,tol;
int bfs()
{
clc(vis,0);
queue<int> q;
tol = 0;
node[tol++] = NODE{1,1%n,-1};
q.push(0);
vis[1%n] = true;
while(!q.empty())
{
int now = q.front();q.pop();
if(0 == node[now].m)
return now;
rep(i,0,2)
{
node[tol] = {i,(node[now].m*10+i)%n,now};
if(!vis[node[tol].m])
{
vis[node[tol].m] = true;
q.push(tol++);
}
}
}
return -1;
}
void out(int u)
{
if(-1 == u) return;
out(node[u].fa);
printf("%d",node[u].val);
}
int main()
{
#ifdef SHY
freopen("d:\\1.txt", "r", stdin);
#endif
scanf("%d", &n);
out(bfs());
putchar('\n');
return 0;
}
/*
536214
4
*/
