Multiple

poj1465:http://poj.org/problem?id=1465

题意：给你一个数n（0~4999）；以及m个不同十进制的数，问有这些十进制数组成的最小的n的倍数是多少。如果有则输出，没有就输出0；

题解：此题用BFS 。。这个题好在 用 余数判重剪枝。。BFS 如果不加以剪枝，一定会搜索的情况会很庞大。所以应该用余数判重 。
为什么可以用余数判重？
   A=a*N +e 即A%N =e
   B= b*N+e即B%N=e
当A  B mod N的余数相同时，如果先出现A 。在A  后加上一个数 i 时 ，  新的数   C = 10 *a*N + 10 *e+i;同样  B后加上数 i 时 ， D = 10*b*N +10*e+i;    由于C D 前边 10*a*N 和 10*b*N 都是N的倍数 ，则C D mod N 的余数都是有 10*e+i 决定的。于是 C D  mod N 同余。因此 A B 同余 都添加上 i 之后 新的两个数C D也是同余的。在无论添加多少个数，新生成的两个数也是同余的。因此 在A 之后如果不出现 N的倍数 ，则在B之后也不会出现。 在A 之后出现，那B之后也会出现。  有因为要求求最小值。所以只需要搜索min（A,B）之后的 ，对于另外一个数之后就不用搜索了。因为对M个排序后，先填入的是小的值，所以 A B 先出现的值小。所以后出现的同余的数 就不用搜索了。因此可以余数判重后剪枝。。。。

#include<cstdio>
#include<stdlib.h>
#include<queue>
#include<cstring>
#define INF 1000000000
using namespace std;
int n,m,d[150]; //d数组用来储存m个数
struct point{
    int yu;//记录余数
    int pre;//记录来自哪一层
    int now; //记录当前的是哪一个d【i】；
}que[10000];
int cmp(const void * a,const void * b){
    int * aa=(int *)a;
    int * bb=(int *)b;
    return *aa-*bb;
}   //比较器从小到大
void print(int tem){
    if(que[tem].pre!=-1){
        print(que[tem].pre);
        printf("%d",que[tem].now);
    }
}//递归输出
int bfs(){
    int front=0,rear=0;
    int flag[5010];//标记是否访问
    que[rear].now=0;
    que[rear].pre=-1;
    que[rear++].yu=0;
    memset(flag,0,sizeof(flag));
    while(front<rear){
        struct point tem;
        tem=que[front];
        for(int i=0;i<m;i++){
            int temp=(tem.yu*10+d[i])%n;
            if(!flag[temp] && (tem.pre!=-1 || d[i]>0)){
                struct point st;
                st.now=d[i];
                st.yu=temp;
                st.pre=front;
                flag[temp]=1;
                que[rear++]=st;
                if(temp==0){
                    print(rear-1);
                    printf("
");
                    return 1;
                }
            }
        }
        front++;
    }
    return 0;
}//在大脑中一定要有完整清晰的思路。
int main(){
    int i;
    while(scanf("%d",&n)!=EOF){
        scanf("%d",&m);
        for(i=0;i<m;i++)
            scanf("%d",&d[i]);
        qsort(d,m,sizeof(d[0]),cmp);
        if(n==0){
            printf("0
");
        }
        else if(!bfs())
            printf("0
");
    }
}