常用算法模板 | 快速幂

vlambda
2020-05-15

常用算法模板 | 快速幂

在给学生讲解2017年普及组初赛“完善程序”第一题的时候，发觉用题目中的程序不太容易讲清楚快速幂算法。事实上，如果用分治的思想，那么写成递归函数更方便理解。而题目中的方法，是把p表示成二进制再拆分。

接下来解释一下快速幂的原理和模板。

假如我们要计算a^b，朴素算法可以通过循环将a连乘b次，时间复杂度为O(b)，当b很大时，这种算法的效率较低。

如果把指数b写成二进制形式，可以将a^b拆分成同底数幂相乘的形式，运算更快。

例如 b = 19 时，b的二进制为10011，即：19 = 1 + 2 + 16，所以，

a^19 = a^(2^0) * a^(2^1) * a^(2^4)。当b的二进制从个位起第 i 位是 1 时，就乘以 a^(2^i)；如果第 i 位是 0 ，则不必相乘。这样只要经过logb次循环就可以计算出结果了。

这一段是将b的二进制倒序输出的代码，同学们非常熟悉。

#include <iostream>
using namespace std;

int main() {
    int b;
    cin >> b;

    while (b) {
        cout << b % 2;
        b /= 2;
    }

    return 0;
}

在这基础上稍做修改，就是快速幂算法的模板，这里1<= a, b, p <= 2*10^9

#include <iostream>
using namespace std;

int main() {
    int a, b, p;
    cin >> a >> b >> p;

    long long res = 1;

    while (b) {
        if (b % 2) res = res * a % p;
        a = (long long)a * a % p;
        b /= 2;
    }

    cout << res;

    return 0;
}