Python 使用分治法求幂

zltzlt

Python 使用分治法求幂

分治法求 x^y：若 y 为偶数，x^y = (x²)^{y // 2}；若 y 为奇数，x^y = x * (x²)^{y // 2}。

代码：

def power(x, y):
    res = 1             # 因为后续是做乘法，所以初始化 res 为 1
    while y:            # 当 y 为 0 时停止循环
        if y % 2:       # 如果 y 是奇数
            res *= x    # res 的值为 res * x
        y //= 2         # y = y // 2，将 y 分成两段
        x *= x          # 分了就得合，这里将 x 合并，即 x = x * x
    return res          # 返回结果 res

永恒的蓝色梦想

不应该是 x^y=(x²)^y//2 和 x^y=x*(x²)^y//2 吗

小马爱python

p是。。。。。