c++入门必学算法之快速幂思想及实现

以下是“C++入门必学算法之快速幂思想及实现”的攻略。

教程概述

快速幂是一种计算幂运算（类似于指数运算）的高效算法。在求解幂运算时，我们通常是采用暴力方法进行连乘，这样的时间复杂度为 $O(n)$，效率较低。而快速幂算法能够在 $O(log_2(n))$ 的时间复杂度内完成幂运算，提高了计算效率。

在本教程中，我们将会介绍快速幂算法的思想和具体实现方法，并提供两条示例说明，帮助大家更好地理解此算法。

快速幂算法思想

快速幂算法的思想是将指数 $n$ 转化为二进制数形式，通过对于每一位的计算结果进行累乘的方式求解幂运算。

例如，当要计算 $a^n$ 时，我们可以将指数 $n$ 转化为二进制数的形式，然后对于每一个非零二进制位 $i$，都计算 $a^{2^i}$，并将结果累乘。例如，当 $n=13$ 时，二进制形式为 $1101$：

$$
a^{13} = a^{2^0} \times a^{2^2} \times a^{2^3}
$$

尽管看起来需要进行 $log_2(n)$ 次计算，但事实上每一次计算都是上一次计算结果的平方，因此在快速幂算法中，只需要使用循环和累乘和平方运算，即可完成高效的幂运算。

快速幂算法实现

以下是快速幂算法的具体实现过程。

long long qmi(long long a, long long b, long long p) {
    long long res = 1 % p;
    while(b) {
        if(b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

函数 qmi 用于计算快速幂运算。

其中，a 表示底数，b 表示指数，p 表示模数。

函数从初始值 res=1 开始循环，每次将指数 $b$ 与 1 做位运算，如果为 1，则将底数乘到结果中，否则不做任何操作。然后对底数进行平方，将指数右移一位，继续循环，直到指数为 0。最后返回结果即可。

示例说明

示例一：求幂模运算

接下来，我们给出一个示例，使用快速幂算法进行幂模运算。

假如我们需要计算 $2^{123456789}$ 除以 $987654321$ 的余数，直接进行连乘显然不可行，此时可以使用快速幂算法来进行快速计算。

首先，我们对 $123456789$ 进行二进制转化。可以得到：

$$
123456789_{10}= 1110101101110111100111010101_{2}
$$

然后使用快速幂算法即可：

long long a = 2, b = 123456789, p = 987654321;
cout<<qmi(a, b, p)<<endl;

输出结果为：

131176846

示例二：使用快速幂算法求斐波那契数列

我们可以用快速幂算法来求解斐波那契数列的第 $n$ 项，而不需要使用递归方法求解大量重复子问题。

斐波那契数列的公式如下：

$$
F_n=F_{n-1}+F_{n-2} \ \ (n>=2,F_0=0,F_1=1)
$$

假设我们需要求解斐波那契数列的第 $10$ 项 $F_{10}$。

使用快速幂算法，可以极大地缩短计算时间复杂度。具体实现如下：

long long a = 1, b = 1, p = 1e9 + 7;
for(int i = 2; i <= 10; i++) {
    int t = b;
    b = (a + b) % p;
    a = t;
}
cout<<b<<endl;

在循环中，我们从 $F_2$ 开始，每次将 $b$ 更新为 $F_{i+1}$，$a$ 更新为 $F_i$（具体原因是为了便于计算），然后通过斐波那契数列的公式进行计算。最终我们能够得到斐波那契数列的第 $10$ 项：

55

总结

本教程主要介绍了快速幂算法的思想和使用方法，并提供了两个示例进行说明。在实际的编程中，快速幂算法具有广泛的应用价值，能够用于高精度计算、求解幂模运算、求解斐波那契数列等问题。