leetcode 483.最小好进制

阅读数: 次 2019-12-20

字数统计: 1.2k字 | 阅读时长: 5分

最小好进制
题目链接
英文链接：https://leetcode.com/problems/smallest-good-base/

中文链接：https://leetcode-cn.com/problems/smallest-good-base/

题目详述
对于给定的整数 n, 如果n的k（k>=2）进制数的所有数位全为1，则称 k（k>=2）是 n 的一个好进制。

以字符串的形式给出 n, 以字符串的形式返回 n 的最小好进制。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

n的取值范围是 [3, 10^18]。
输入总是有效且没有前导 0。、

题目详解

本题是寻找一个数最小的good base。其定义是对于一个数y，其x进制表示为全1，则称x是y的good base。应该比较好理解，其实就是将y写成1+x+x^2 +…+x^(n-1)，就是一个等比数列求和，于是我们可以将其转化为y = (x^n - 1)/(x - 1)，其中x>=2, 3<y<10^18,为了寻找最小的x，我们可以先来确定一下n的取值范围，很明显x越小n越大，所以当x=2时，n最大为log2(y+1)。从第三个例子可以看出来，当x=y-1时，n最小为2。所以有了n的取值范围我们就可以遍历所有可能的n，然后每次循环中y和n都是确定值，在对x使用二叉搜索确定其值即可。

这里有两个变量，一个是进制，一个是对应进制下的长度。可以固定一个变量，然后判断是否满足条件即可。进制的取值范围为 [2, n - 1]，范围太大，所以应该固定长度，判断是否存在满足条件的进制。进制越小，长度越长；进制越大，长度越短。我们可以从大到小枚举长度，判断是否存在满足条件的进制，这一步可以运用二分查找。

枚举长度的时间复杂度为 O(logn)，二分查找的时间复杂度为 O(logn)，辅助计算的时间复杂度为 O(logn)，总的时间复杂度为 O(logn ^ 3)。

另外一个需要注意的问题就是，因为本题中的数都比较大，所以要注意溢出问题，之前也做过一到这种题，可以使用java内置的BigInteger类进行处理。代码如下所示：

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);
    }
}

不过看题解的时候看到一个大佬的神仙解法，如下

有点类似于梯度下降

假设有两个变量x, y，求解方程 f(x, y) = z
当f(x, y)相对于x和y都是单调的时候
则可以先固定x，求下一个满足条件的y边界，然后固定y求下一个满足条件的x边界，

这样不断逼近最终解

class Solution {
public:
    using ll = long long;
    ll nextK(ll k, ll m, ll N, bool& match) {
        match = false;
        ll lo = k + 1;
        ll hi = N - 1;
        while (lo <= hi) {
            ll md = lo + (hi - lo) / 2;
            ll s = 0;
            for (ll i = 0; i <= m; ++i) {
                if (s > (N - 1) / md) {
                    s = N + 1;
                    break;
                }
                s = s * md + 1;
            }
            if (s == N) {
                match = true;
                return md;
            }
            if (s > N) hi = md - 1;
            else lo = md + 1;
        }
        return lo;
    }
    ll nextM(ll k, ll m, ll N, bool& match) {
        match = false;
        ll lo = 1;
        ll hi = m - 1;
        while (lo <= hi) {
            ll md = lo + (hi - lo) / 2;
            ll s = 0;
            for (ll i = 0; i <= md; ++i) {
                if (s > (N - 1) / k) {
                    s = N + 1;
                    break;
                }
                s = s * k + 1;
            }
            if (s == N) {
                match = true;
                return md;
            }
            if (s > N) hi = md - 1;
            else lo = md + 1;
        }
        return hi;
    }
    string smallestGoodBase(string n) {
        ll N = stoll(n);
        ll k = 2;
        ll m = N; // m为N表示为k进制的最高次幂
        bool match = false;
        while (k < N && m > 0) {
            m = nextM(k, m, N, match);
            if (match) break;
            k = nextK(k, m, N, match);
            if (match) break;
        }
        return to_string(k);
    }
};