0483. Smallest Good Base¶
题目信息¶
- 题号:
0483
- 难度:
Hard
- 主题:
大整数、进制表示、全为 1、最小底数
- 原题:
- 重点:
底数必须至少为 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)。