（详细）快速幂算法及效率分析大数幂乘快速幂取余（附测试时间）

快速幂

问题：求a^b % m，即a的b次方对m取余的结果。

只要学过C语言的循环就可以写出最简单的朴素版本：

朴素版

typedef long long LL;
LL normal_Edition(LL a, LL b, LL m)
{//朴素版本LL ans = 1;for(int i = 0; i < b; ++i)ans *= a;ans = ans % m;return ans;
}


时间复杂度O（b），空间复杂度达到了惊人的O（a^b）的指数级。

考虑问题规模：a <(10 ^ 9)， b <(10 ^ 6)，m <(10 ^ 9)。

问题出现了：这样的算法在求a的b次幂的时候就极其容易溢出，即便用long long也是如此。

我们有取模运算的运算法则：
(a * b) % p = (a % p * b % p) % p

在这里不加证明的使用。

所以在这个前提下，我们可以在求a的b次幂的同时，每次对m进行%操作，这样可以使得ans不会越界。

根据思想可以写出以下代码：

改进版

LL advanced_Edition(LL a, LL b, LL m)
{//普通优化LL ans = 1;for(int i = 0; i < b; ++i)ans = ans * a % m;return ans;
}


时间复杂度O（b），空间复杂度为的O（max（a，m）），此时溢出的问题是得到了解决。

但如果考虑问题规模：a <(10 ^ 9)， b <(10 ^ 18)，m <(10 ^ 9)，这样显然又无法满足需要了。

快速幂

这时候引入快速幂，它基于二分的思想，所以也称为二分幂。

不难注意到这样的事实：求a^b的过程中，b只有两种情况：奇数或偶数。

若b为偶数，则a^b = a^(b/2) * a^(b/2)。

若b为奇数，则a^b = a * a ^ (b-1)。且从下一次开始，b必然为偶数的情况。

基于以上思想就可以成功把求幂过程的复杂度降为（logb）。这样就可以满足原规模的数据了。

根据思想写出以下递归版本代码：

递归版：

LL fast_Rec_Edition(LL a, LL b, LL m)
{//快速幂 递归实现LL ans = 1;if(b == 0) return 1;if(b & 1) return a * fast_Rec_Edition(a, b - 1, m) % m; // 奇数，用位运算更快else{LL mul = fast_Rec_Edition(a, b / 2, m);return mul * mul % m;//这一步一定不能写成//return fast_Rec_Edition(a, b / 2, m) * fast_Rec_Edition(a, b / 2, m);//这样会每次多次调用，使得复杂度回归O（b）}return ans;
}


我们也可以进一步写出迭代版本的代码（From算法笔记）：

迭代版：

LL fast_Iter_Edition(LL a, LL b, LL m)
{//快速幂迭代实现LL ans = 1;while(b){if(b & 1) // 最低位是1ans = ans * a % m;a = a * a % m; // a²， %m防止溢出b >>= 1; // 右移}return ans;
}


性能测试

#include
using namespace std;typedef long long LL;//求 a^b % m 的几种写法及复杂度分析
LL normal_Edition(LL a, LL b, LL m)
{//朴素版本LL ans = 1;for(int i = 0; i < b; ++i)ans *= a;ans = ans % m;return ans;
}LL advanced_Edition(LL a, LL b, LL m)
{//普通优化LL ans = 1;for(int i = 0; i < b; ++i)ans = ans * a % m;return ans;
}LL fast_Rec_Edition(LL a, LL b, LL m)
{//快速幂 递归实现LL ans = 1;if(b == 0) return 1;if(b & 1) return a * fast_Rec_Edition(a, b - 1, m) % m;else{LL mul = fast_Rec_Edition(a, b / 2, m);return mul * mul % m;}return ans;
}LL fast_Iter_Edition(LL a, LL b, LL m)
{//快速幂迭代实现LL ans = 1;while(b){if(b & 1)ans = ans * a % m;a = a * a % m;b >>= 1;}return ans;
}int main()
{time_t start, over;LL a, b, m = 7, ans;scanf("%lld %lld %lld", &a, &b, &m);//-----------------------------------------------------------------start = clock();ans = normal_Edition(a, b, m);over = clock();printf("使用朴素版, %lld^%lld %% %lld = %lld所用时间为 %f s\n", a, b, m, ans, (double)(over - start)/CLOCKS_PER_SEC);//-----------------------------------------------------------------start = clock();ans = advanced_Edition(a, b, m);over = clock();printf("使用优化版, %lld^%lld %% %lld = %lld所用时间为 %f s\n", a, b, m, ans, (double)(over - start)/CLOCKS_PER_SEC);//-----------------------------------------------------------------start = clock();ans = fast_Rec_Edition(a, b, m);over = clock();printf("使用快速幂递归版, %lld^%lld %% %lld = %lld所用时间为 %f s\n", a, b, m, ans, (double)(over - start)/CLOCKS_PER_SEC);//-----------------------------------------------------------------
//-----------------------------------------------------------------start = clock();ans = fast_Iter_Edition(a, b, m);over = clock();printf("使用快速幂迭代版, %lld^%lld %% %lld = %lld所用时间为 %f s\n", a, b, m, ans, (double)(over - start)/CLOCKS_PER_SEC);
//-----------------------------------------------------------------return 0;
}

两组测试

1：10000 ^ 500000000 mod 71

朴素版已由于溢出导致结果错误，而优化版虽然能得出正确答案，但耗时相当长，快速幂的两种实现几乎没有任何耗时。

2：1003 ^ 9223372036854775807 mod 71

总结：

快速幂/二分幂的思想还是非常有用的，同时作为简单的算法也值得了解。

递归/迭代的写法在效率上差距不明显，可以采用自己习惯的写法。