题意：求m的倍数中不包含一些数码的最小倍数数码是多少。比如15 ，不包含0 1 3，答案是45.
BFS过程：用b[]记录可用的数码。设一棵树，树根为-1.树根的孩子是所有可用的数码，孩子的孩子也是所有可用的数码。这样从根到叶子节点这条路径所组成的数表示一个可行的数。
__ __
剪枝：(A % m == B % m) => (AX % m == BX % m) 即如果搜索到一个数X, X%m == a (a !=0) , 则以后如果搜索到Y , Y%m == a,则不必继续搜索。 这样一棵树是有尽头的。
所有这棵树的节点最多才m-1个。
这个剪枝在逻辑电路课上突然灵光突现，昨天模拟赛就怎么也想不来了，额，熬夜要变傻子了。 还有碰到两个陷阱，m==0的时候要特判。不能用节点来直接保存答案，long long 不够用，递归输出答案吧。
#include <stdio.h> #include <string.h> //#include <queue> using namespace std; #define MAXN 100005 int N,m; bool vis[MAXN]; int pre[MAXN]; int a[102]; int b[102]; int num[MAXN]; int que[MAXN]; int front,rear; void print(int x) //递归从前往后输出答案 { if (pre[x] != -1 ) print(pre[x]); printf("%d",num[x]); return; } int main() { int i,j,k,x,cas=0; int casb,ans; while (scanf("%d%d",&N,&m)!=EOF) { printf("Case %d: ",++cas); int x; int casb=0; memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); memset(vis,0 , sizeof(vis)); for (i=0; i<m; i++) { scanf("%d",&x); a[x]=1; } for (i = 0; i <= 9; i++) if (a[i] == 0) b[casb++]=i; if (N == 0) //特判 { if (b[0] == 0) printf("0 "); else printf("-1 "); continue; } int flag=1; int ans; front=0;rear=0; for (i = 0; i < casb; i++) //最高位 if (b[i]!=0) { que[rear++]=b[i]%N; vis[b[i]%N]=true; num[rear-1]=b[i]; pre[rear-1]=-1; if (b[i] % N == 0) { ans=b[i]; flag=0; break; } } if (flag == 0) { printf("%d ",ans); continue; } int tmp; ans=-1; flag=0; while (front != rear) //bfs { tmp=que[front]; for (i = 0; i < casb; i++) if (!vis[(tmp*10+b[i]) % N]) //剪枝 { que[rear]=(tmp*10+b[i])% N; vis[(tmp*10+b[i])% N ]=true; pre[rear] = front;//保存父节点 num[rear] = b[i]; //保存本节点这个位数的数字 if ((tmp*10+b[i]) % N == 0) { print(rear); printf(" "); flag=1; break; } rear++; } if (flag) break; front++; } if (flag == 0) printf("-1 "); } return 0; }