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