快速幂

要求 , 其中 , . 先不妨假设 , 基本想法是

很容易写出时间复杂度 的递归算法, 而要写迭代算法需要再想一想.

迭代

用二进制表示指数 , 其中 , 则 .

以 10 为例, 把它转化成二进制数.

由于 10 是偶数, 所以 .

由于 10/2 是奇数, 所以 .

由于 (5-1)/2 是偶数, 所以 .

由于 2/2 是奇数, 所以 .

由此

class Solution:
    def myPow(self, a: float, n: int) -> float:
        if n>= 0:
            res = 1
            while n:
                if n % 2:
                    res *= a
                n //= 2
                a *= a
            return res
        else:
            return 1/self.myPow(a, -n)

另外, Python 对小整数乘法有优化 (见 这里). 就 3.7 版本来说, 下面前两句时间一样, 后两句时间一样, 所以没有必要强行把代码写成位运算.

for _ in range(int(1e8)):
    7777777 >> 1
    
for _ in range(int(1e8)):
    7777777 // 2

for _ in range(int(1e8)):
    7777777 & 1
    
for _ in range(int(1e8)):
    7777777 % 1

取模

若

考虑 , , 其中 立即可以看出.

由此易知 对 取模的算法.