ZOJ Problem Set – 1136 Multiple Time Limit: 10 SecondsMemory Limit: 32768 KB
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 file 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:
Input
22 3 7 0 1
2 1 1
Output
110 0 Source: Southeastern Europe 2000 Submit Status 主要是剪枝：数论的剪枝，直接用例子解释，比如36%24==12==60%24，那么36*****%24==60******%24 比如 368%24==608%24，所以在搜索的时候，如果已经搜索到36%24==12，那么遇到60时可以直接跳过
;maxn=100002;const int inf=9999999;int n,m;int a[maxn];int mod[maxn];int getMode(string s){int len=s.size();int ans=0;for(int i=0;i<len;i++){ans=(ans*10+s[i]-‘0′)%n;}return ans;}string bfs(){cl(mod,0);queue<string> q;for(int i=0;i<m;i++){//初始化队列的起点q.push(string(1,a[i]+’0′));//string(number,char)构造函数}while(!q.empty()){string s=q.front();q.pop();if(s!=”0″&&getMode(s)==0){return s;}for(int i=0;i<m;i++){string tmp=s;if(tmp==”0″&&a[i]==0)continue;//特判，，防止出现00000…的情况tmp+=string(1,a[i]+’0’);int d=getMode(tmp);if(mod[d]++)continue;//出现同余，直接跳过q.push(tmp);}}return “0”;}int main(){while(~scanf(“%d”,&n)){scanf(“%d”,&m);for(int i=0;i<m;i++){scanf(“%d”,&a[i]);}if(n==0){printf(“0\n”);continue;}sort(a,a+m);printf(“%s\n”,bfs().c_str());}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
正确的寒暄必须在短短一句话中明显地表露出你对他的关怀。
