LeetCode 483题 “Smallest Good Base” 是一个中等难度的数学问题。题目要求找到一个最小的“好基数”（good base），使得给定的正整数 ( N ) 可以表示为以下形式：

[ N = a^0 + a^1 + a^2 + \ldots + a^d ]

其中 ( a ) 是基数，( d ) 是指数的最大值，且 ( a ) 和 ( d ) 都是正整数。

题目描述

给定一个正整数 ( N )，找到最小的“好基数” ( a )。

解题思路

1. 数学转换：
   • 首先，将等式转换为数学形式： [ N = \frac{a^{d+1} – 1}{a – 1} ]
   • 这个等式表示 ( N ) 可以被表示为 ( a ) 的等比数列之和。
2. 确定范围：
   • 对于给定的 ( N )，我们需要找到合适的 ( d ) 和 ( a )。
   • ( d ) 的最大值可以通过 ( 2^d \leq N ) 来估算，因为 ( a ) 至少为2。
3. 二分查找：
   • 对于每个可能的 ( d )，使用二分查找来确定合适的 ( a )。
   • 二分查找的范围是 ( [2, N^{1/d}] )。
4. 验证：
   • 对于每个 ( a )，验证等式 ( N = \frac{a^{d+1} – 1}{a – 1} ) 是否成立。

代码实现

以下是 Python 的实现代码：

class Solution: def smallestGoodBase(self, N: int) -> str: import math

    def check(a, d):
        # 检查是否满足等式 N = a^0 + a^1 + ... + a^d
        sum = 0
        for i in range(d + 1):
            sum = sum * a + 1
        return sum == N

    def find_a(d):
        # 使用二分查找找到合适的 a
        left, right = 2, int(N**(1/d)) + 1
        while left < right:
            mid = (left + right) // 2
            sum = (mid**(d+1) - 1) // (mid - 1)
            if sum == N:
                return mid
            elif sum < N:
                left = mid + 1
            else:
                right = mid
        return -1

    # 从大的 d 开始尝试，找到最小的 a
    for d in range(int(math.log2(N)), 1, -1):
        a = find_a(d)
        if a != -1:
            return str(a)

    # 如果没有找到，返回 N-1（根据题意，这种情况不会发生）
    return str(N - 1)

sol = Solution() print(sol.smallestGoodBase(13)) # 输出 "3" print(sol.smallestGoodBase(4681)) # 输出 "8"

解释

1. check函数：
   • 用于验证给定的 ( a ) 和 ( d ) 是否满足等式。
2. find_a函数：
   • 使用二分查找来确定合适的 ( a )。
3. 主函数：
   • 从大的 ( d ) 开始尝试，找到最小的 ( a )。
   • ( d ) 的范围从 ( \log_2(N) ) 开始向下递减，因为 ( d ) 越大，( a ) 越小。

复杂度分析

• 时间复杂度：( O(\log^2(N)) )，因为 ( d ) 的范围是 ( O(\log(N)) )，每次二分查找的时间复杂度是 ( O(\log(N)) )。
• 空间复杂度：( O(1) )，使用了常数空间。

通过上述步骤和代码实现，可以有效地解决 LeetCode 483题 “Smallest Good Base”。