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
思路：
設(shè)基數(shù)為X
首先 如果兩個數(shù)對bs取模相等(為M） 則
A = aX + M
B = bX + M
那么只要其中一個可以取到結(jié)果 即
（10*（bX + M）+ C）MOD X = 0
也就是（10*M）MOD X?+ C MOD X = 0
則另一個必定也可以整除 X
這樣在搜索的時候如果只需要搜索A （假設(shè)A<B) 就可以了
也就是說如果我們按照BFS擴展 把狀態(tài)設(shè)置為MOD值 則只需要M的長度的隊列就可以完成這個搜索了
無解的情況如何？自然就是無法擴展的情況。至于是否要優(yōu)化最后一層（即搜索到了所有的非0 mod值 我認為沒有必要）
注意不要把一個5000的字符串和其mod數(shù)封裝在一起作為隊列元素 會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;
}
寫這個的時候發(fā)現(xiàn)一首很好聽的歌
《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..