python实现快速幂

若需要计算a^b，如果使用循环来计算显然效率是很低的

以下有三种方法实现快速幂

方法一，python自带函数pow(a,b,mod)，其中a为底数，b为指数，mod是对该数取模，mod参数有时候可以不传

a=pow(5,9)

方法二，利用递归实现快速幂，该方法需要注意分类讨论，考虑到指数为0，指数为1以及指数是奇数的情况

def fast_power(a,b,mod):
    if b==0:
        return 1%mod
    if b==1:
        return a%mod
    ans=fast_power2(a,b//2,mod)%mod
    ans=ans*ans
    if b%2==1:
        ans*=a%mod
    return ans%mod

方法三，利用指数的二进制，快速计算

如假设a=3，b=13 13的二进制是1101 所以3^13=3^8*3^4*3^1 相当于是看二进制哪一位是1 指数就是2的多少次方

def fast_power(a,b):
    res=1
    while b:
        if b&1:
            res*=a
        a=a*a
        b>>=1
    return res