Python经典算法-快速幂

快速幂

问题描述：
计算a ** n % b 其中a、b和n都是32位的非负整数
即求a的n次方对b的余数
问题示例：
例如：2**31%3=2

代码实现如下

class Solution:
    def fastPower(self, a, b, n):
        ans = 1
        while n > 0:
            if n % 2 == 1:
                ans = ans * a % b
            a = a * a % b
            n = n / 2
        return ans % b


if __name__ == '__main__':
    solution = Solution()
    print(solution.fastPower(2, 31, 3))

实现结果

快速幂代码也可以写成（采用位运算，容易理解）

def fastPower2(self,a,b,n):
    ans = 1
    base = a
    while n != 0:
        if (n & 1 != 0):
            ans *= base
        base *= base
        n >>= 1
    return ans % b
# 或者
def fastPower3(self,a,b,n):
    ans = 1
    base = a
    while n != 0:
        if (n & 1 != 0):
            ans *= base % b
        base *= base % b
        n >>= 1
    return ans % b

具体的思路可以看这个博文
大家可以看到两个方法在取余的地方不太一样，其实方法一用了取余的运算法则，把取余展开计算了。