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