4106973_ac_422ms_5428k.java

北大大牛代码 1240道题的原代码 超级权威

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	private Scanner in;

	private BigInteger[] r = new BigInteger[200];
	
	private BigInteger[] tmp = new BigInteger[200];
		
	private static final BigInteger ONE = BigInteger.ONE;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		new Main().run();
	}

	private void run() {
		// TODO Auto-generated method stub
		in = new Scanner(System.in);
		int num;

		while (true) {
			num = in.nextInt();
			if (num == 0) {
				break;
			}
			Arrays.fill(r, null);
			int rm = 1;
			r[1 % num] = ONE;
			String n = "1";
			while (r[0] == null) {
				Arrays.fill(tmp, null);
				rm = rm * 10 % num;
				n += "0";
				boolean mark = true;
				if (r[rm] == null) {
					r[rm] = new BigInteger(n);
					mark = false;
				}
				for (int i = 0; i < num; i++) {
					if (r[i] != null && (i != rm || mark)) {
						int t = (i + rm) % num;
						if (r[t] == null) {
							tmp[t] = r[i].add(new BigInteger(n));
						}
					}
				}
				for (int i = 0; i < num; i++) {
					if (tmp[i] != null) {
						r[i] = tmp[i];
					}
				}
			}
			System.out.println(r[0]);
		}
	}

}