http://poj.org/problem?id=1465
Multiple
| Time Limit: 1000MS |
|
Memory Limit: 32768K |
| Total Submissions: 6164 |
|
Accepted: 1339 |
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 Source Southeastern Europe 2000 |
题意：
给出一个整数N，和M个0～9的数，求N的一个最小倍数，且该数仅由这M个数构成，不存在则输出0。
分析：
如果存在最终的数，一定可以写成A1*10^(k-1)+A2*10^(k-2)+...+Ak,Ai属于给出的M个数的集合。k有可能很大，64位整数也可能存不下。注意到最后的结果是N的倍数，假设结果是X，则有X%N=0,注意到结果的多项式形式，显然能想到使用同余定理。我们需要从1位扩展到k位（当然要一步步来），可以用BFS，用余数来记录状态（只需要第一个），这样状态不超过N个，一旦余数为0,我们需要的结果就出来了。
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include