0483. Smallest Good Base

题目信息

题号:

0483

难度:

Hard

主题:

大整数、进制表示、全为 1、最小底数

原题:

LeetCode 0483

重点:

底数必须至少为 2、表示需包含至少两个数字 1、输入和输出都是十进制字符串、返回最小可行底数

题目重述

给定表示整数 N 的十进制字符串 n。若在底数 k >= 2 的进制中,N 的表示由两个或更多连续数字 1 组成,则称 k 是 N 的好进制。返回最小的好进制,并使用十进制字符串表示。

等价地,需要找到最小 k 和某个整数 m >= 1,使:

N = 1 + k + k^2 + ... + k^m

N 位于 [3, 10^18]。不能因输入超过普通 32 位整数范围而丢失精度;结果返回的是底数,不是该进制下的表示字符串。

自建示例

存在三位全一表示:

输入:n = "13"
输出:"3"
解释:13 = 1 + 3 + 3^2,所以在三进制中表示为 111;不存在更小的合法底数。

二进制就是最小好进制:

输入:n = "31"
输出:"2"
解释:31 = 1 + 2 + 4 + 8 + 16,在二进制中为 11111,而底数不能小于 2。

枚举全 1 表示的位数并二分底数

若表示中有 terms 个连续的 1,则必须满足 N = 1 + k + ... + k^(terms-1)。底数越大,这个和严格增加,因此固定 terms 后可以在 [2, N-1] 上二分寻找精确底数。为了得到最小底数,应从较大的 terms``(更多位的全 1 表示)向下枚举;最后 ``terms = 2 一定给出 k = N - 1。

计算几何和时使用“超过目标就立即停止”的乘法检查,避免 k 的高次幂溢出 64 位整数。最多需要考虑的位数是 N 的二进制位数,因为底数至少为 2。

C++ 实现

class Solution {
    long long target;

    long long geometricSum(long long base, int terms) {
        long long power = 1;
        long long sum = 1;
        for (int i = 1; i < terms; ++i) {
            if (power > target / base) return target + 1;
            power *= base;
            if (sum > target - power) return target + 1;
            sum += power;
        }
        return sum;
    }

public:
    std::string smallestGoodBase(std::string n) {
        target = std::stoll(n);
        int maxTerms = 0;
        for (long long value = target; value > 0; value >>= 1) {
            ++maxTerms;
        }

        for (int terms = maxTerms; terms >= 2; --terms) {
            long long left = 2;
            long long right = target - 1;
            while (left <= right) {
                long long base = left + (right - left) / 2;
                long long sum = geometricSum(base, terms);
                if (sum == target) return std::to_string(base);
                if (sum < target) {
                    left = base + 1;
                } else {
                    right = base - 1;
                }
            }
        }
        return std::to_string(target - 1);
    }
};

代码分析

固定位数时几何和关于底数单调,二分不会漏掉该位数的唯一候选;从位数多到少搜索,则首次命中的底数小于所有更短表示的底数。乘法前用 target / base 判断下一幂是否会超过目标,保证中间值不溢出。位数枚举和二分共同带来 O(log^2 N) 时间,额外空间复杂度为 O(1)。