PKU1465 Multiple

Multiple
Time Limit:1000MS? Memory Limit:32768K
Total Submit:992 Accepted:221

Description
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).

Input
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.

Output
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:

Sample Input

22
3
7
0
1

2
1
1

Sample Output

110
0
思路：
设基数为X
首先 如果两个数对bs取模相等(为M） 则
A = aX + M 
B = bX + M
那么只要其中一个可以取到结果 即
（10*（bX + M）+ C）MOD X = 0
也就是（10*M）MOD X?+ C MOD X = 0
则另一个必定也可以整除 X
这样在搜索的时候如果只需要搜索A （假设A<B) 就可以了
也就是说如果我们按照BFS扩展 把状态设置为MOD值 则只需要M的长度的队列就可以完成这个搜索了
无解的情况如何？自然就是无法扩展的情况。至于是否要优化最后一层（即搜索到了所有的非0 mod值 我认为没有必要）
注意不要把一个5000的字符串和其mod数封装在一起作为队列元素 会TLE的 呵呵
Solution：
//by Optmistic
#include <algorithm>
using namespace std;
const int N = 5010;
struct E{char num; int m; E * f;};
E q[N];
int cd[10], X;
bool chk[N];
void print(const E e) {
?if(e.f)?{
??print(*e.f);
??printf("%c", e.num);
?}
}
int main() {
?int i, nc;
?while(scanf("%d", &X)!=EOF) {
??scanf("%d", &nc);
??memset(chk, 0, sizeof(chk));
??for(i = 0; i<nc; i++)
???scanf("%d", cd+i);
??if(X == 0) {printf("0\n");continue;}
??sort(cd, cd+nc);
??int qs = 0, qe = 1;
??q[0].m = 0;
??q[0].f = NULL;
??E * first = &q[0];
??while(qs < qe) {
???E cur = q[qs];
???E now;
???now.f = &q[qs];
???int m = cur.m;
???for(i = 0; i< nc; i++) {
????int s = (10*m+cd[i])%X;
????if(!chk[s] && (now.f != first || cd[i] > 0) ) {
?????now.m = s;
?????now.num = cd[i]+'0';
?????q[qe++] = now;
?????chk[s] = 1;
?????if(s == 0) {
??????print(now);
??????putchar('\n');
??????goto HERE;
?????}
????}
???}
???qs++;
??}
HERE:??if(qs == qe) printf("0\n");
?}
?return 0;
}
写这个的时候发现一首很好听的歌 
《No promises》
shayne ward

Hey baby, when we are together, doing things that we love.
Every time you're near I feel like I’m in heaven, feeling high
I don’t want to let go, girl.
I just need you to know girl.
I don’t wanna run away, baby you’re the one I need tonight,
No promises.
Baby, now I need to hold you tight, I just wanna die in your arms
Here tonight
Hey baby, when we are together, doing things that we love.
Everytime you're near I feel like I’m in heaven, feeling high
I don’t want to let go, girl.
I just need you you to know girl.
I don’t wanna run away, baby you’re the one I need tonight,
No promises.
Baby, now I need to hold you tight, I just wanna die in your arms
I don’t want to run away, I want to stay forever, thru Time and Time..
No promises
I don’t wanna run away, I don’t wanna be alone
No Promises
Baby, now I need to hold you tight, now and forever my love
No promises
I don’t wanna run away, baby you’re the one I need tonight,
No promises.
Baby, now I need to hold you tight, I just wanna die in your arms
I don’t wanna run away, baby you’re the one I need tonight,
No promises.
Baby, now I need to hold you tight, I just wanna die in your arms
Here tonight..