介绍

快速幂（Exponentiation by squaring，平方求幂）是一种简单而有效的小算法，它可以以O(log n)的时间复杂度计算乘方。快速幂不仅本身非常常见，而且后续很多算法也都会用到快速幂。

为什么要使用快速幂？

比如要计算以下式子：

传统算法是

计算机要通过9次计算才能得出答案。而快速幂的方法就是通过平方来减少计算次数：

这样子就只需要4次。

这样的时间复杂度是O(log n)，当次方很大时可以节省很多时间。

算法实现

非递归版
1
2
3
4
5
6
7
8
9
10
fast_power(a, b)
	ans = 1
    while(b)
        if b % 2 == 1	//当幂为奇数时
            ans *= a
            b -= 1
        else
            a *= a
            b /= 2
    return ans

在b % 2 == 1运行完成后，b必定是偶数，接下来会再次进行while循环进入到else里面，其实我们可以简化成一次循环，如下：

1
2
3
4
5
6
7
8
fast_power(a, b)
	ans = 1
    while(b)
        if b % 2 == 1
            ans *= a
        a *= a
        b /= 2
    return ans
递归版（慎用）
1
2
3
4
5
6
7
8
fast_power(a, b)
	if b <= 0
    	return 1
    if b % 2 == 1	//当幂为奇数时
    	ans = fast_power(a, b - 1) * a
    else 
    	ans = fast_power(a * a, b / 2)
    return ans

以上都要注意变量a, b, ans的范围。

例题a^b

题目：牛客网

输入描述：

三个用空格隔开的整数a,b和p。

输出描述：

一个整数，表示a^b mod p的值。

思路：

  1. 最直接的思路就是算出a^b的值之后再模p，不管是否上述快速幂的方法，都存在一个很明显问题是 a^b 的范围大至10的9次方的10的9次方，远超过了long long的范围。

  2. 利用快速幂+取模运算的性质，可以快速的同时不会让数值超过范围，性质(a b) % p = (a % p b % p) % p

    于是可以得到以下代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    typedef long long ll;
    ll fast_power(ll a, ll b, ll p) {
    	ll ans = 1;
    	a %= p;
    	while(b) {
    		if(b % 2 == 1) 
    			ans = (ans * a) % p;
    		a = (a * a) % p;
    		b /= 2;
    	}
    	return ans % p;
    }

  3. 其实还可以使用位运算，提升运行的速度，代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    typedef long long ll;
    ll fast_power(ll a, ll b, ll p) {
    	ll ans = 1;
    	a %= p;
    	while(b) {
    		if(b & 1) 		// 如7二进制为0000 0111，1二进制为0000 0001，则7&1 = 0000 0001 = 1
    			ans = (ans * a) % p;
    		a = (a * a) % p;
    		b >>= 1;		// 7二进制为0000 0111，向右位移一位为 0000 0011 = 3 （不足补0）
    	}
    	return ans % p;
    }

    常见的位运算符有 与& 或| 右移>> 左移<< 异或^

最终代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>

using namespace std;

typedef long long ll;

ll fast_power(ll a, ll b, ll p) {
    a %= p;
    ll ans = 1;
    while(b) {
        if(b & 1)
            ans = (ans * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return ans % p;
}

int main() {
    
    ll a, b, p;
    
    cin >> a >> b >> p;
    
    cout << fast_power(a, b, p);
    
    return 0;
}

参考资料：

[1] Pecco : 算法学习笔记(4)：快速幂

[2] 芸学习 : 【C++/算法】快速幂算法详解