​LeetCode刷题实战483：最小好进制

示例 1：

输入："13"
输出："3"
解释：13 的 3 进制是 111。

示例 2：

输入："4681"
输出："8"
解释：4681 的 8 进制是 11111。

示例 3：

输入："1000000000000000000"
输出："999999999999999999"
解释：1000000000000000000 的 999999999999999999 进制是 11。

import java.math.BigInteger;

class Solution {
    public static String smallestGoodBase(String n) {
        //现将字符串解析成long型数据
        long s = Long.parseLong(n);
        //对所有可能的指数n进行遍历
        for (int max_e = (int) (Math.log(s) / Math.log(2)) + 1; max_e >= 2; max_e--) {
            long low = 2, high = s, mid;
            //进行二叉搜索，寻找最小的good base。
            while (low <= high) {
                mid = low + (high - low) / 2;
                //一开始没有使用BigInteger，会报错
                BigInteger left = BigInteger.valueOf(mid);
                left = left.pow(max_e).subtract(BigInteger.ONE);
                BigInteger right = BigInteger.valueOf(s).multiply(BigInteger.valueOf(mid).subtract(BigInteger.ONE));
                int cmr = left.compareTo(right);
                if (cmr == 0)
                    return String.valueOf(mid);
                else if (cmr > 0)
                    high = mid - 1;
                else
                    low = mid + 1;
            }
        }
        return String.valueOf(s - 1);
    }
}