51nod1109

【题意】给定一个自然数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
*/