如何实现受限递归函数判断x是否为b的幂，复杂度要求O(logb*logx)？

现有代码问题分析 #

你当前的实现每次递归调用add(b, b)等价于将b乘以2，本质上是判断x是否等于b * 2^k，仅当b本身是2的幂时才可能得到正确结果，没有用到题目允许的乘法工具函数，逻辑完全不符合要求。

正确实现思路 #

我们采用递归倍增幂次+快速校验的方案，完全符合运算限制，且时间复杂度达标：

1. 核心逻辑：我们要找是否存在自然数n使得b^n =x，通过递归倍增b的幂次快速逼近x，避免循环和额外运算符
2. 所有运算仅使用题目允许的%判奇偶、add（两数相加）、multiply（两数相乘）、div2（整数除以2）工具函数，无其他自定义数学运算

完整代码实现 #

# 工具函数说明（题目已提供，无需自行实现）：
# add(a, b): 返回a + b
# multiply(a, b): 返回a * b
# div2(a): 返回a // 2（整数除法，向下取整）

# 辅助函数：判断a是否能被b整除，可整除则返回商，否则返回-1
def div_check(a, b):
    if a < b:
        return 0 if a == 0 else -1
    if a == b:
        return 1
    half_a = div2(a)
    half_res = div_check(half_a, b)
    if half_res == -1:
        return -1
    double_res = multiply(half_res, 2)
    if multiply(double_res, b) == a:
        return double_res
    full_res = add(double_res, 1)
    if multiply(full_res, b) == a:
        return full_res
    return -1

# 主函数
def is_power(b, x):
    # 边界条件处理
    if x == 1:
        # 任何数的0次幂都是1，若题目要求n为正自然数，此处改为return b == 1即可
        return True
    if b == 1:
        # 1的任何次幂都是1
        return x == 1
    if x < b:
        return False
    if x == b:
        return True
    # 优先校验b^2的幂，降低递归深度
    square_b = multiply(b, b)
    if square_b <= x:
        if is_power(square_b, x):
            return True
    # 若平方幂不匹配，校验x是否能被b整除，递归判断商是否为b的幂
    quotient = div_check(x, b)
    if quotient == -1:
        return False
    return is_power(b, quotient)

时间复杂度说明 #

1. 每次递归优先判断平方幂，递归深度为O(log log x)
2. 单次div_check的递归深度为O(log x)
3. 整体时间复杂度为O(log b * log x)，完全符合题目要求。

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