Multiple

Time Limit: 1000MS		Memory Limit: 32768K
Total Submissions: 7183		Accepted: 1540

a program that, given a natural number N between 0 and 4999 (inclusively), and M distinct decimal digits X1,X2..XM (at least one), finds the smallest strictly positive multiple of N that has no other digits besides X1,X2..XM (if such a multiple exists).

The input has several data sets separated by an empty line, each data set having the following format:


On the first line - the number N

On the second line - the number M

On the following M lines - the digits X1,X2..XM.

For
each data set, the program should write to standard output on a single
line the multiple, if such a multiple exists, and 0 otherwise.



An example of input and output:

22

3

7

0

1

2

1

1

110

0
题意：用下面所给的数字这些数构成的数字中找到是k的最小的倍数，每个数能用多次。
思路：bfs；
首先如果k为0的时候需要特判，然后将所给的数按升序排列，然后BFS的时候就能保证先被广搜到的数小。
然后这样会爆，所以需要剪枝。
我们要找的是k的倍数，那么这个数modk=0；然后看到k的范围很小。
假如两个数A，B；
A=n*k+s;B=m*k+s;
也就是A=B（modk）;那么当这两数去搜下一层的时候，A*10+b[i]；
B*10+b[i]；那么这两个数对于k取余相等，所以我们只要将小的数加入队列。那么每个模数在队列中就出现一次就行，队列中的元素最多k个
还有这个数了可能很大，所以用静态数组记录前驱去找数。
C++超时，G++100多MS

  1 #include <cstdio>

  2 #include <cstdlib>

  3 #include <cstring>

  4 #include <cmath>

  5 #include <iostream>

  6 #include <algorithm>

  7 #include <map>

  8 #include <queue>

  9 #include <vector>

 10 #include<set>

 11 using namespace std;

 12 typedef long long LL;

 13 bool flag[6000];

 14 int ans[20];

 15 set<int>que;

 16 set<int>::iterator it;

 17 typedef struct pp

 18 {

 19         int mod;

 20         int id;

 21         int pre;

 22         int digit;

 23         pp()

 24         {

 25             pre=-1;

 26         }

 27 } ss;

 28 ss bns[1000000];

 29 int ask[1000000];

 30 int cp[2000000];

 31 int  bfs(int n,int m);

 32 int main(void)

 33 {

 34         int i,j,k;

 35         while(scanf("%d",&k)!=EOF)

 36         {

 37                 int n;

 38                 int m;

 39                 que.clear();

 40                 scanf("%d",&n);

 41                  for(i=0;i<n;i++)

 42                  {

 43                      scanf("%d",&cp[i]);

 44                  }

 45                  sort(cp,cp+n);

 46                  ans[0]=cp[0];

 47                 int uu=cp[0];

 48                 int t=1;

 49                  for(i=1;i<n;i++)

 50                  {

 51                      if(cp[i]!=uu)

 52                      {

 53                          ans[t++]=cp[i];

 54                          uu=cp[i];

 55                      }

 56                  }

 57

 58                 if(k==0)printf("0\n");

 59                 else

 60                 {

 61                         int sum=0;

 62                         int id=bfs(t,k);

 63                         if(id==-1)

 64                         {

 65                                 printf("0\n");

 66                         }

 67                         else

 68                         {

 69                                 while(id!=-1)

 70                                 {

 71                                         ask[sum++]=bns[id].digit;

 72                                         id=bns[id].pre;

 73                                 }

 74                                 for(i=sum-1; i>=0; i--)

 75                                 {

 76                                         printf("%d",ask[i]);

 77                                 }

 78                                 printf("\n");

 79                         }

 80                 }

 81         }

 82         return 0;

 83 }

 84 int  bfs(int n,int m)

 85 {

 86         int i,j,k;

 87         int kk=0;

 88         memset(flag,0,sizeof(flag));

 89         queue<ss>stc;

 90         for(i=0; i<n; i++)

 91         {

 92                 int mod=ans[i]%m;

 93                 if(!flag[mod]&&ans[i]!=0)

 94                 {

 95                         flag[mod]=true;

 96                         bns[kk].id=kk;

 97                         bns[kk].mod=mod;

 98                         bns[kk].pre=-1;

 99                         bns[kk].digit=ans[i];

100                         stc.push(bns[kk]);

101                         kk++;

102                 }

103         }

104         while(!stc.empty())

105         {

106                 ss tt=stc.front();

107                 stc.pop();

108                 for(i=0; i<n; i++)

109                 {

110                         int mod=(tt.mod*10+ans[i])%m;

111                         if(!flag[mod])

112                         {

113                                 bns[kk].id=kk;

114                                 bns[kk].pre=tt.id;

115                                 bns[kk].mod=mod;

116                                 bns[kk].digit=ans[i];

117                                 if(mod==0)

118                                 {

119                                         return kk;

120                                 }

121                                 stc.push(bns[kk]);

122                                 kk++;

123                                 flag[mod]=true;

124                         }

125                 }

126         }

127         return -1;

128 }