问题描述

首先我们来看一道题目:

有三个整数a,b,m，求a^b%m的值。 (注: a^b意为a的b次方)

这道题目一开始看上去很简单，只要写一个简单的循环就能够搞定。

long long f(long long a,long long b,long long m){
    long long res=1;
    for(long long i=1;i<=b;i++){
        res=res*a;
    }
    return res%m;
}

如果你这么写，那你就肯定没有考虑到数据范围，比如说f(2,200,3)，返回的结果会是0。

原因很简单，这样res变量会非常大，以至于超出了long long类型数据范围。

那么，我们应该如何解决这个问题呢？这里我们需要运用取模运算的性质：

$ (a + b) \mod p = (a \mod p + b \mod p) \mod p $ $ (a - b) \mod p = (a \mod p - b \mod p ) \mod p $ $ (a \times b) \mod p = (a \mod p \times b \mod p) \mod p $

将上面的代码稍作修改：

long long f(long long a,long long b,long long m){
    long long res=1;
    for(long long i=1;i<=b;i++){
        res=res*a;
        res=res%m; //加入一行
    }
    return res%m;
}

再次运行程序，f(2,200,3)返回的结果是1，这次是正确的。

但是，这个程序运行起来很慢，是不可取的。

快速幂算法

我们应该都知道，$ a^{m+n}=a^{m} \times a^{n} $ ,$ a^{m \times n}=(a^m)^n $。快速幂的思想就是，将幂的指数用二进制表示，分割成更小的任务。

例如，计算$2^{12}$，首先将指数12转为二进制数1100，然后按位乘以权值，分成8和4两个数。

$2^{12} = 2^{8} \times 2^{4} $

$2^1=2$

$2^2=(2^1)^2=4$

$2^4=(2^2)^2=16$

$2^8=(2^4)^2=256$

即$2^{12}=256 \times 16=4096$

观察上述算式，可以总结出：

1. 当指数为偶数时，$a^b=(a^{b/2})^2$

2. 当指数为奇数时，由于b/2余1，应当再乘以底数，即$a^b=(a^{b/2})^2 \times a$

我们用递归实现以上过程，加上每一步的取模：

long long ksm(long long a,long long b,long long m){
    if(b==0)return 1;
    long long res=ksm(a,b/2,m)%m;
    if(b%2==1)return ((res*res)%m*a%m)%m; //指数为奇数
    else return (res*res)%m; //指数为偶数
}

代码优化

非递归式通常会比递归要快一点，同时我们使用位运算，可以使速度大幅提升。

改进后的最终代码如下：

long long ksm(long long a,long long b,long long m){
    long long res=1;
    while(b>0){
        if(b&1)res=res*a%m;
        a=(a*a)%m;
        b>>=1;
    }
    return res%m;
}

具体程序运行速度可以自行对比，可以说，最终优化的快速幂可以极其快速地处理很大的数据。