UVa 107 - The Cat in the Hat

// UVa 107 - The Cat in the Hat

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

public class Main {

	private static final BigInteger TWO = BigInteger.valueOf(2);
	private static final int MAX_EXPONENT = 10000;

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		BigInteger heightOfTheInitialCat = scanner.nextBigInteger();
		BigInteger numberOfWorkerCats = scanner.nextBigInteger();
		while (isNotZero(heightOfTheInitialCat) && isNotZero(numberOfWorkerCats)) {

			CatSums catSums = calculateCatSums(heightOfTheInitialCat, numberOfWorkerCats);
			System.out.println(catSums.nonWorkingCats + " " + catSums.heights);

			heightOfTheInitialCat = scanner.nextBigInteger();
			numberOfWorkerCats = scanner.nextBigInteger();
		}

		scanner.close();
	}

	private static CatSums calculateCatSums(BigInteger heightOfTheInitialCat, BigInteger numberOfWorkerCats) {
		if (isOne(heightOfTheInitialCat) && isOne(numberOfWorkerCats))
			return CatSums.of(BigInteger.ZERO, BigInteger.ONE);
		if (isOne(numberOfWorkerCats))
			return CatSums.of(BigInteger.valueOf(log(TWO, heightOfTheInitialCat)),
					heightOfTheInitialCat.multiply(TWO).subtract(BigInteger.ONE));

		SolutionPair pair = solve(heightOfTheInitialCat, numberOfWorkerCats);
		BigInteger n = pair.n;
		BigInteger nPlus1 = n.add(BigInteger.ONE);
		int x = pair.x;

		BigInteger nonWorkingCatsInThisLevel = BigInteger.ONE;
		BigInteger nonWorkingCatsSum = nonWorkingCatsInThisLevel;

		BigInteger heightInThisLevel = heightOfTheInitialCat;
		BigInteger sumOfHeights = heightInThisLevel;

		for (int i = 1; i <= x; i++) {
			nonWorkingCatsInThisLevel = nonWorkingCatsInThisLevel.multiply(n);
			nonWorkingCatsSum = nonWorkingCatsSum.add(nonWorkingCatsInThisLevel);
			heightInThisLevel = heightInThisLevel.divide(nPlus1);
			sumOfHeights = sumOfHeights.add(heightInThisLevel.multiply(nonWorkingCatsInThisLevel));
		}

		nonWorkingCatsSum = nonWorkingCatsSum.subtract(numberOfWorkerCats);

		return CatSums.of(nonWorkingCatsSum, sumOfHeights);
	}

	public static SolutionPair solve(BigInteger b, BigInteger a) {
		int y = log(TWO, b);
		for (int x = y; x >= 1; x--) {
			BigInteger nPlus1 = root(b, x);
			BigInteger n = nPlus1.subtract(BigInteger.ONE);
			if (n.pow(x).compareTo(a) >= 0 && nPlus1.pow(x).compareTo(b) == 0) {
				return SolutionPair.of(n, x);
			}
		}
		return SolutionPair.of(b.subtract(BigInteger.ONE), 1);
	}

	/**
	 * Finds the n-th root of radicand i.e. finds x such that x^n = radicand
	 */
	private static BigInteger root(BigInteger radicand, int n) {
		BigInteger left = TWO, right = radicand, sol = BigInteger.ONE;
		while (left.compareTo(right) <= 0) {
			BigInteger mid = left.add(right).divide(TWO);
			BigInteger power = mid.pow(n);
			if (power.compareTo(radicand) == 0)
				return mid;
			else if (power.compareTo(radicand) < 0) {
				sol = mid;
				left = mid.add(BigInteger.ONE);
			} else {
				right = mid.subtract(BigInteger.ONE);
			}
		}
		return sol;
	}

	private static int log(BigInteger base, BigInteger x) {
		if (base.equals(x))
			return 1;
		if (isOne(x))
			return 0;
		if (x.compareTo(base) < 0)
			return 0;

		int left = 1, right = MAX_EXPONENT, sol = 1;
		while (left <= right) {
			int mid = (left + right) / 2;
			BigInteger power = base.pow(mid);
			if (power.compareTo(x) == 0)
				return mid;
			else if (power.compareTo(x) < 0) {
				sol = mid;
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}
		return sol;
	}

	private static boolean isNotZero(BigInteger bigInt) {
		return BigInteger.ZERO.compareTo(bigInt) != 0;
	}

	private static boolean isOne(BigInteger bigInt) {
		return BigInteger.ONE.compareTo(bigInt) == 0;
	}

	public static class SolutionPair {
		public final BigInteger n;
		public final int x;

		private SolutionPair(BigInteger n, int x) {
			this.n = n;
			this.x = x;
		}

		public static SolutionPair of(BigInteger n, int x) {
			return new SolutionPair(n, x);
		}

	}

	public static class CatSums {
		public final BigInteger nonWorkingCats;
		public final BigInteger heights;

		private CatSums(BigInteger nonWorkingCats, BigInteger heights) {
			this.nonWorkingCats = nonWorkingCats;
			this.heights = heights;
		}

		public static CatSums of(BigInteger nonWorkingCats, BigInteger heights) {
			return new CatSums(nonWorkingCats, heights);
		}

	}

}