题目描述:
给你两个正整数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)
快速幂:
我们先来了解两个小东西。
ab * ab = a2b
ab * ab * a = a2b+1
把这两个公式倒过来,就奠定了快速幂的基础。
ab = ab/2 * ab/2
ab = ab/2 * ab/2 * a
对于上面的两个公式,我们注意到 当前 幂次方的 奇偶性,对于我们的运算有一定的影响。
所以我们首先判断一下 b 是奇数还是偶数,如果是偶数就直接减半,是奇数我们就减1后再减半,直到b=0
的是时候,就可以结束循环了。
根据这样的一个分析,我们可以写出一个关于递归循环的一个代码。有兴趣的同学可以尝试一下。
接着我们再分析一下,假设现在 b = 9
.
a9 = a4 * a4 * a
a4 = a2 * a2
a2 = a * a
一共做了3次减半,1 次减1。
也就是相当于从小开始做了 1次加1,3次翻倍。
pos & 1
是位运算 中的与运算, 常用来判断奇偶性。
pos >>= 1
是位运算中的 右移,相当于 pos //= 2
有些同学可能会有疑问, 我们的每一次循环都会执行一下 num=num*num
,而只有奇数的时候才会执行 res = res * num
, 最后 res 和 num 会合在一起吗?
这个是肯定的,因为最后一次循环的时候 b 一定等于1 。
这里再给出 a15 的模拟,各个变量的值,帮助大家的理解。
b | num | res |
---|---|---|
15 | a | 1 |
7 | a*a | a |
3 | a * a * a * a | a * a * a |
1 | a * a * a * a * a * a * a * a | a * a * a * a * a * a * a |
0 | a * a * a * a * a * a * a * a * a * a * a * a * a * a * a * a | a * a * a * a * a * a * a * a * a * a * a * a * a * a * 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))