pythonTip 33 大幂次运算

题目描述：

给你两个正整数a(0 < a < 100000)和n(0 <= n <=100000000000)，计算(a^n) % 20132013并输出结果

示例：

输入：a = 3453 n = 0

输出：1

分析：

一般情况下幂运算可以用循环一次一次的去计算。

例如: a^b次方

1
2
3

ans = 1
for i in range(b):
    ans *= a

但是如果对于特别大的数的时候，使用模拟方法，就会消耗大量的时间了。例如：如果b=100000000000,那么我们就需要循环100000000000次，并且做100000000000次的乘法，这样就比较消耗时间了。因此我们需要一个快速的办法，去做幂运算 —– 这个方法就叫做快速幂。

循环模拟的时间复杂度是O(n), 而快速幂的时间复杂度是Olog(n)

快速幂：

我们先来了解两个小东西。

1. a^b * a^b = a^2b

2. a^b * a^b * a = a^2b+1

把这两个公式倒过来，就奠定了快速幂的基础。

1. a^b = a^b/2 * a^b/2

2. a^b = a^b/2 * a^b/2 * a

对于上面的两个公式，我们注意到 当前 幂次方的 奇偶性，对于我们的运算有一定的影响。

所以我们首先判断一下 b 是奇数还是偶数，如果是偶数就直接减半，是奇数我们就减1后再减半，直到b=0 的是时候，就可以结束循环了。

根据这样的一个分析，我们可以写出一个关于递归循环的一个代码。有兴趣的同学可以尝试一下。

接着我们再分析一下，假设现在 b = 9.

a⁹ = a⁴ * a⁴ * a

a⁴ = a² * a²

a² = a * a

一共做了3次减半，1 次减1。

也就是相当于从小开始做了 1次加1，3次翻倍。

pos & 1 是位运算 中的与运算， 常用来判断奇偶性。

pos >>= 1 是位运算中的 右移，相当于 pos //= 2

有些同学可能会有疑问， 我们的每一次循环都会执行一下 num=num*num，而只有奇数的时候才会执行 res = res * num, 最后 res 和 num 会合在一起吗？

这个是肯定的，因为最后一次循环的时候 b 一定等于1 。

这里再给出 a¹⁵ 的模拟，各个变量的值，帮助大家的理解。

有兴趣的同学可以自己再模拟一遍。

分析:

1
2
3
4
5
6
7
8
9
10

def mode(num, pos, mod):
    res = 1
    while pos > 0:
        if pos & 1:
            res = (res * num) % mod
        pos >>= 1
        num = (num * num) % mod
    return res % mod

print(mode(a, n, 20132013))