求优化：实现O(log k)复杂度的最小k满足n^k≥m（禁用内置函数）

给定自然数n、m，确定满足n^k ≥ m的最小自然数k，要求时间复杂度为O(log k)，且不能使用内置函数。目前仅能实现O(k)时间复杂度的版本，请求帮助优化。现有代码如下：

def potnr(a, b):
    rez = 1
    while b>0:
        if b%2:
            rez = rez * a

        b = b // 2
        a = a * a
        
    return rez

def liczba(n, m):
    k = 1
    while potnr(n, k) < m:
        k += 1

    return k

print(liczba(2, 16))

你当前的liczba函数通过逐个递增k来验证条件，时间复杂度是O(k)，可以用二分查找把时间复杂度降到O(log k)级别，核心是先快速确定k的范围，再在范围内精准查找最小符合条件的k，结合你已经实现的快速幂potnr就能完成。

具体思路 #

1. 快速确定k的上限：从k=1开始，不断倍增k，直到n^k ≥ m。这个过程只需要O(log k)次循环，就能找到一个足够大的右边界。
2. 二分查找最小k：在左边界1和找到的右边界之间，用二分法缩小范围：每次取中间值mid，用potnr计算n^mid，如果满足n^mid ≥ m，就尝试找更小的k（缩小右边界）；如果不满足，就增大左边界。最终左边界就是我们要找的最小k。

优化后的代码 #

def potnr(a, b):
    rez = 1
    while b > 0:
        if b % 2:
            rez = rez * a
        b = b // 2
        a = a * a
    return rez

def liczba(n, m):
    # 特殊情况：m<=1时，n^0=1≥m，最小k为0
    if m <= 1:
        return 0
    # n=1时，只有m<=1才有解，否则无满足条件的自然数k
    if n == 1:
        return float('inf') if m > 1 else 0
    
    # 先找右边界：倍增直到n^right >= m
    right = 1
    while potnr(n, right) < m:
        right *= 2
    
    # 二分查找最小k
    left = 1
    while left < right:
        mid = (left + right) // 2
        current = potnr(n, mid)
        if current >= m:
            right = mid
        else:
            left = mid + 1
    return left

# 测试
print(liczba(2, 16))  # 输出4
print(liczba(3, 20))  # 输出3（3^3=27≥20）
print(liczba(5, 1))   # 输出0

说明 #

• 特殊情况处理覆盖了边界场景，避免逻辑漏洞；
• 倍增找右边界的步骤确保我们不会浪费时间在过大的范围上；
• 二分查找的每一步都用快速幂计算，整体时间复杂度是O((log k)^2)，属于log级别的复杂度，远优于原有的O(k)实现。

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