ZJU PAT 1010 Radix

题目见：http://pat.zju.edu.cn/contests/pat-a-practise/1010

本题采用二分方法搜索进制，注意由于我使用的方法是转换为十进制进行比较，所以C/C++中即使使用了long long 类型也可能会溢出，为方便起见，本题采用Java的BigInteger实现；或者可以考虑自己实现一个大数类。

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

public class Main{
	private static BigInteger bs0 = new BigInteger("0");
	private static BigInteger bs1 = new BigInteger("1");
	private static BigInteger bs2 = new BigInteger("2");

	// Or you can use: Character.getNumericValue(c)
	private static int charToInt(char c) {
		return c <= '9' ? (c - '0') : (c - 'a' + 10);
	}

	private static BigInteger getBigIntegerBased10(int val) {
		return new BigInteger(String.valueOf(val));
	}

	private static BigInteger getNumber(String s, BigInteger radix) {
		BigInteger t = bs0;
		BigInteger p = bs1;
		char c;
		BigInteger temp;
		for (int i = s.length() - 1; i >= 0; i--) {
			c = s.charAt(i);
			temp = getBigIntegerBased10(charToInt(c));
			t = t.add(temp.multiply(p));
			p = p.multiply(radix);
		}
		return t;
	}

	private static void handle(String a, String b, int radix) {
		char c = b.charAt(0);
		BigInteger v1 = getNumber(a, getBigIntegerBased10(radix));
		if (b.length() == 1) {
			int bv = charToInt(c);
			if (v1.intValue() == bv) {
				System.out.println(bv + 1);
			} else {
				System.out.println("Impossible");
			}
			return;
		}

		for (int i = 1; i < b.length(); i++) {
			if (b.charAt(i) > c)
				c = b.charAt(i);
		}
		// Determine the lower bound of the radix
		BigInteger l = getBigIntegerBased10(charToInt(c) + 1);
		BigInteger r = v1;// Determine the upper bound of the radix
		// System.out.println(l + " : " + r);
		BigInteger m, v2;
		while (l.compareTo(r) <= 0) {
			m = l.add(r).divide(bs2);
			v2 = getNumber(b, m);
			if (v1.equals(v2)) {
				System.out.println(m);
				return;
			} else if (v1.compareTo(v2) < 0) {
				r = m.subtract(bs1);
			} else {
				l = m.add(bs1);
			}
		}
		System.out.println("Impossible");
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String a = scanner.next();
		String b = scanner.next();
		int tag = scanner.nextInt();
		int radix = scanner.nextInt();
		if (tag == 1)
			handle(a, b, radix);
		else
			handle(b, a, radix);
	}

}