难度: Hard
以字符串的形式给出 n , 以字符串的形式返回 n 的最小 好进制 。
如果 n 的 k(k>=2) 进制数的所有数位全为1，则称 k(k>=2) 是 n 的一个 好进制 。
示例 1：
输入：n = "13" 输出："3" 解释：13 的 3 进制是 111。
示例 2：
输入：n = "4681" 输出："8" 解释：4681 的 8 进制是 11111。
示例 3：
输入：n = "1000000000000000000" 输出："999999999999999999" 解释：1000000000000000000 的 999999999999999999 进制是 11。
提示：
n 的取值范围是 [3, 1018]n 没有前导 0运行时间: 32 ms
内存: 16.0 MB
class Solution:
def smallestGoodBase(self, n: str) -> str:
num = int(n)
# n = x^(m-1) + x^(m-2) + ... + x + 1
for m in range(num.bit_length(),2,-1):
# 二项式展开 x^(m-1) < n < (x+1)^(m-1)
x = int(pow(num,1/(m-1)))
# 等比数列求和 n = (x^m - 1)/(x-1)
if num == (pow(x,m) - 1)//(x-1):
return str(x)
return str(num-1)
题解利用等比数列的求和公式，结合枚举所有可能的数列长度 m (从 n 的二进制长度递减至 2) 来找到最小的好进制。对于每个 m，首先计算可能的基数 x = n的(m-1)次方根，然后验证 x 是否能够使得 n 等于从 1 到 x^(m-1) 的等比数列和。如果满足条件，即为所求的最小好进制。
时间复杂度: O(log(n))
空间复杂度: O(1)
class Solution:
def smallestGoodBase(self, n: str) -> str:
num = int(n) # 将输入的字符串 n 转化为整数
# 遍历所有可能的数列长度 m，从 n 的二进制位长度开始，直至 2
for m in range(num.bit_length(), 2, -1):
# 计算 m-1 次方根，得到可能的基数 x
x = int(pow(num, 1/(m-1)))
# 判断是否满足等比数列求和公式 n = (x^m - 1)/(x-1)
if num == (pow(x, m) - 1) // (x-1):
return str(x) # 如果满足条件，返回 x 作为最小好进制
return str(num-1) # 如果没有找到符合条件的 x，返回 n-1
在题解中，为了找到合适的基数 `x` 使等式 `n = (x^m - 1) / (x - 1)` 成立，首先需要确定序列的长度 `m`。给定长度 `m` 后，可以将公式重写为 `x^m - 1 = n * (x - 1)`，进而估算基数 `x`。利用 `x` 的最大可能值为 `n` 的 `(m-1)` 次方根，可以通过计算 `int(pow(num, 1/(m-1)))` 来近似得到 `x`。这种估算是基于等比数列求和公式的数学推导，确保 `x` 和 `m` 的选择能满足原始等式。
选择从 `n` 的二进制长度递减至 2 遍历 `m` 是基于最小好进制的特性。当 `n` 用二进制表示时，长度最长时其基数为 `2`，这是可能的最大长度。从这个长度开始递减至 2，可以有效地找到最小的 `m` 使得存在对应的基数 `x`。这种递减遍历方式有助于尽快找到满足条件的最小 `x`，因为较小的 `m` 对应较大的 `x`，而我们的目标是找到最小的好进制，即最小的 `x`。从效率上看，这种方法减少了不必要的计算，因为从小的 `m` 开始并不总是能迅速找到满足条件的基数。
计算 `x` 为 `n` 的 `(m-1)` 次方根可能在精度上存在问题，特别是当 `m` 较大或 `n` 较大时，由于浮点数运算的精度限制，计算得到的 `x` 可能不是整数或者四舍五入后的结果可能与实际的整数解有差距。这种不准确性可能导致无法准确验证 `n = (x^m - 1) / (x - 1)`。为了改进这个问题，可以采用整数二分查找方法来更精确地寻找可能的基数 `x`。在一个合理的范围内（例如从 `2` 到 `n-1`），通过二分查找逐步逼近正确的 `x`，同时每次迭代都验证是否满足等比数列求和公式，这样可以更精确地确定 `x`。