首页 > 代码库 > poj 1465 & zoj 1136 Multiple (BFS+余数重判)
poj 1465 & zoj 1136 Multiple (BFS+余数重判)
Multiple
| Time Limit: 1000MS | Memory Limit: 32768K | |
| Total Submissions: 6177 | Accepted: 1346 |
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
223701211
Sample Output
1100
知识点：用到一个余数定理吧。 假设 x%n = e， y%n = e，那么 （x*10+k）%n = （e*10+k）%n = （y*10+k）%n。
题目意思：给你m个数字（0~9），判断他们能否组成n的最小倍数。
解题思路：因为要是最小的，所以我们先对这m个数就行排序，那样得到的倍数肯定是最小的，还有就是，最重要的一点就是用到余数重判，若余数之前出现过，就不需要再判断了，这里进行了剪枝。还有就是poj要自己写queue而zoj则可以用STL中的queue。
贴出代码：
#include <stdio.h>#include <stdlib.h>#include <string.h>struct Node{ int pre; //前一个数的位置 int remainder; //取得的余数 int digit; //当前这个数的值} node[5005];int num[15], mark[5005];int cmp(const void * a, const void * b){ return *(int *)a - *(int *)b;}void Output(int rear) //将所求得的数输出{ if(node[rear].pre != -1) { Output(node[rear].pre); printf("%d", node[rear].digit); }}void BFS(int n,int m){ struct Node temp; //进行初始化操作 int front = 0, rear = 1, Rem; memset(mark, 0, sizeof(mark)); node[0].pre = -1; node[0].remainder = 0; while(front < rear) { for(int i = 0; i<m; i++) { Rem = (node[front].remainder*10+num[i])%n; //取余 if(!mark[Rem] && (node[front].pre!=-1 || num[i]>0)) //确保第一个数字不为0，和余数重判剪枝 { mark[Rem] = 1; temp.pre = front; temp.remainder = Rem; temp.digit = num[i]; node[rear++] = temp; if(Rem == 0) //找到了最小的倍数 { Output(rear-1); printf("\n"); return ; } } } front++; } printf("0\n");}int main(){ int n, m; while(scanf("%d", &n)!=EOF) { scanf("%d", &m); for(int i = 0; i<m; i++) { scanf("%d", &num[i]); } qsort(num, m, sizeof(num[0]), cmp); //对数组进行升序排序，以确保是最小的倍数 if(n == 0) printf("0\n"); else BFS(n, m); } return 0;}