Multiple
|
Time Limit: 1000MS |
Memory Limit: 32768K |
|
Total Submissions: 5911 |
Accepted: 1284 |
Description
a program that, given anatural number N between 0 and 4999 (inclusively), and M distinct decimaldigits X1,X2..XM (at least one), finds the smallest strictly positive multipleof N that has no other digits besides X1,X2..XM (if such a multiple exists).
Input
The input has several datasets 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 programshould write to standard output on a single line the multiple, if such amultiple 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
题目大意：
给定一个数N（0<=N<=4999）,现在给定若干个十进制的数，能否用给定的十进制的数组成一个数，使其是N的倍数，如果存在，请求出倍数最小的数，如果不存在，请输出0；
十进制的数可以无限次重复使用，例如N=22；用7，0，1三个十进制的数可以组成110使其是22的最小的倍数；
该题必须解决两个问题：
1， 怎么判断不存在该数的倍数，也就是说在什么情况下可以停止遍历；
2， 因为数的可能大小非常大，我们不能用int来存储，那么需要怎么解决这个问题；
3， 如何保证取出的数是最小的额
取余数操作，从个位数开始，对每个数取余，若余数不为零，那么对每个余数添加增加所有的可能性，依次无线循环；何时结束呢？就是取余的时候，如果发现该余数已经是第二次出现了，那么可以丢弃，因此也就是说，最多需要遍历4999次，把所有的余数都取了一遍；
存数，我们可以用数组来存储每一位数，不妨新建一个类，每一种组合新建一个类；类包含成员prev，指向上一个数，打个比方，首次遍历 分别为数1,7新建一个类，他们的prev指向空，数1又能衍生出3个类，数1,0,7,此时他们的prev分别指向数1；同时也要有成员modNum保存当前的余数，也要有一个成员currentNum表示当前的数是多少。
为了保证取出的数是最小的，我们给这些十进制的数排序，每次取数从小开始取数，因为是fifo队列，所以总是从最小的计算；
开始动手写代码吧。。。
Java代码如下：
import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
// 用来标记所有的余数，比如余数32，可以表示allModNum[32]=1;表示已经存在
private int[] allModNum;
// 这是存放十进制数的数组；
private int[] number;
private int N;
public Main(int N) {
this.N = N;
if (N != 0) {
allModNum = new int[N];
Arrays.fill(allModNum, 0);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner cin = new Scanner(new BufferedInputStream(System.in));
int N ;
while (cin.hasNext()) {
N = cin.nextInt();
Main ma = new Main(N);
int countNum;
countNum = cin.nextInt();
ma.number = new int[countNum];
for (int i = 0; i < countNum; i++) {
ma.number[i] = cin.nextInt();
}
ma.processItBfsAndPrint();
}
}
private void processItBfsAndPrint() {
// TODO Auto-generated method stub
// 辅助实现的队列;
LinkedList<Node> al = new LinkedList<Node>();
Arrays.sort(number);
// 这个事特例哈；
if (N == 0) {
System.out.println(0);
return;
}
Arrays.fill(allModNum, 0);
if (number[0] != 0) {
if (number[0] % N == 0) {
System.out.println(number[0]);
return;
}
al.add(new Node(null, number[0] % N, number[0]));
allModNum[number[0] % N] = 1;
}
for (int i = 1; i < number.length; i++) {
if (number[i] % N == 0) {
System.out.println(number[i]);
return;
}
al.add(new Node(null, number[i] % N, number[i]));
allModNum[number[i] % N] = 1;
}
Node nodetemp;
int modTemp;
while (al.size() > 0) {
nodetemp = al.remove();
for (int i = 0; i < number.length; i++) {
modTemp = (nodetemp.modNum * 10 + number[i]) % N;
// 这就是我们需要的值；
if (modTemp == 0) {
// 用来暂时保存所有的值
ArrayList<Integer> ans = new ArrayList<Integer>();
ans.add(number[i]);
while (nodetemp != null) {
ans.add(nodetemp.currentNum);
nodetemp = nodetemp.prev;
}
for (int j = ans.size() - 1; j >= 0; j--) {
System.out.print(ans.get(j));
}
System.out.println();
return;
}
if (allModNum[modTemp] == 0) {
allModNum[modTemp] = 1;
al.add(new Node(nodetemp, modTemp, number[i]));
}
}
}
System.out.println(0);
}
static class Node {
private Node prev;
private int modNum;
private int currentNum;
public Node(Node prev, int modNum, int currentNum) {
this.prev = prev;
this.modNum = modNum;
this.currentNum = currentNum;
}
}
}
Chapter05-Multiple（POJ 1465）,布布扣,bubuko.com
原文：http://blog.csdn.net/haizi8888/article/details/23607741