python 幂运算(python中幂的表示方法)

使用快速幂的原因，针对高次幂计算，如果使用循环遍历的方法，时间开销比较大eg:8^10000000000 而使用快速幂的方法可以在O(log(次幂））的复杂度内完成。

import time
start=time.time()
p=1000000007
def quick_count(a,b):
    sum=1
    while b!=0:
        if b&1:
            sum=sum*a%p
        b>>=1
        a*=a#注意是x自身，容易写成x2, x2对应到阶乘下+1而非x2
    return sum
print(quick_count(2,10000000))
print(time.time()-start)

说明eg:2^8 8=>1000

2^8=>（（2^4）^2））
（（（2^2）^2）^2）
迭代过程：
2 (2)^2 (2^2)^2 (2^2^2)^2

对比一般遍历程序：

import time
start=time.time()
p=1000000007
def quick_count(a,b):
    sum=1
    for i in range(0,b):
        sum=sum*a%p
    return sum
print(quick_count(2,10000000))
print(time.time()-start)