如何优化寻找十进制数全1表示最小进制的Python代码？

问题分析 #

原代码的核心瓶颈在于：当输入大数且不存在3位及以上全1表示时，需要遍历从2到sqrt(n)的所有进制，单次遍历的数位检查也存在冗余运算，导致整体耗时极高。优化的关键在于减少枚举次数和提升单次检查效率。

具体优化步骤 #

1. 优化数位检查函数

将原有的check_digits改为直接逐位判断是否为1，一旦发现非1位立即返回，避免乘法操作，逻辑更简洁高效：

def is_all_ones(n: int, base: int) -> bool:
    while n > 0:
        if n % base != 1:
            return False
        n = n // base
    return True

2. 改变枚举策略：从枚举进制到枚举位数

全1数字在进制base下的k位表示满足公式：
$$S_k = 1 + base + base^2 + ... + base^{k-1} = \frac{base^k - 1}{base-1} = n$$
我们可以枚举k（位数）而非base，k的最大取值为log2(n+1)（因为2进制的k位全1数是最小的k位全1数），这个范围远小于sqrt(n)，通常不超过50次枚举。

3. 二分查找对应进制

对于每个k，利用全1数随base增大单调递增的特性，用二分法快速定位满足条件的base，避免遍历所有可能值。同时在计算全1数的和时，中途若和超过n则立即终止，减少不必要运算。

4. 快速小范围检查

先快速检查小范围的进制（如2到100），对于存在小进制解的情况直接返回，无需进入后续的二分流程。

优化后的完整代码 #

def is_all_ones(n: int, base: int) -> bool:
    while n > 0:
        if n % base != 1:
            return False
        n = n // base
    return True

def get_min_base(n: int) -> int:
    if n == 1:
        return 2  # 特殊情况处理：1可表示为任意进制的1，这里返回最小合法进制2
    
    # 先快速检查小范围进制，快速返回常见解
    max_small_base = min(101, n)
    for base in range(2, max_small_base):
        if is_all_ones(n, base):
            return base
    
    min_base = n - 1  # 默认返回2位全1的进制（n-1）
    k_max = n.bit_length()  # 最大可能的位数：2^(k_max-1) <= n < 2^k_max
    
    # 从最大位数往下枚举，找到的第一个解就是最小进制
    for k in range(k_max, 2, -1):
        low = 2
        # 计算进制的上限：base^(k-1) <= n → base <= n^(1/(k-1))
        high = int(n ** (1 / (k - 1))) + 2
        if high < low:
            continue
        
        while low <= high:
            mid = (low + high) // 2
            current_sum = 1
            term = 1
            overflow = False
            
            # 递推计算全1数的和，中途超过n则终止
            for _ in range(k - 1):
                term *= mid
                current_sum += term
                if current_sum > n:
                    overflow = True
                    break
            
            if overflow:
                high = mid - 1
            elif current_sum == n:
                return mid
            else:
                low = mid + 1
    
    return min_base

优化效果 #

• 对于存在3位及以上全1表示的大数，通过枚举位数+二分查找，将时间复杂度从$O(\sqrt{n})$降至$O(\log n \cdot \log n)$，速度提升几个数量级。
• 对于不存在3位及以上全1表示的大数，无需遍历到sqrt(n)，仅需几十次枚举即可确认，避免了大量无效运算。

内容的提问来源于stack exchange，提问作者Evil Baboon