【算法笔记·数论】快速幂，加速幂运算，超级详细。C/C++

2023-01-04 11:20:44

前言：

欢迎光临大千小熊的博客，我是一只又会MMD又会C++的正派熊，B站和CSDN同步更新，欢迎关注。

幂运算含义：

形如 x n x^n xn 指数是x，底数是x的一个幂。（ n n n是变量）
例如 2 4 = 16 ， 2 2 = 4 2^4=16，2^2=4 24=16，22=4这样的运算。

计算幂运算的方法：

例如，我们想去计算 2 4 2^4 24。我们可以循环4次，另res=1，然后res*=4。
但是这样的算法是不高效率的。
这是因为，我们想计算 2 ∗ 2 ∗ 2 ∗ 2 2*2*2*2 2∗2∗2∗2的时候，人类一般都会用 2 ∗ 2 = 4 2*2=4 2∗2=4，然后是 4 ∗ 4 = 16 4*4=16 4∗4=16。来计算答案，这样只需要两步。这个方法的时间复杂度比上面算法的时间复杂度小，而且是因为拆开成两个部分，因此新的算法复杂度是 l o g ( x ) log(x) log(x)级别的。而最先的那个笨方法是 x x x级别的。

那么我们怎么做到那样的巧妙的方法去计算快速幂呢？
请看下面的内容。

快速幂的设计思想：

例如上面的例子 2 ∗ 2 ∗ 2 ∗ 2 2*2*2*2 2∗2∗2∗2。我们可以设计一个递归函数。来不停的拆分上面的算式。
设函数 Q u i c k P o w ( x , n ) QuickPow(x,n) QuickPow(x,n)表示 x n x^n xn的结果。下一个状态是 Q u i c k P o w ( x ∗ x , n / 2 ) QuickPow(x*x,n/2) QuickPow(x∗x,n/2)。
那么 Q u i c k P o w ( 2 , 4 ) QuickPow(2,4) QuickPow(2,4)意思就是上面的 2 ∗ 2 ∗ 2 ∗ 2 2*2*2*2 2∗2∗2∗2。
然后 Q u i c k P o w ( 4 , 2 ) QuickPow(4,2) QuickPow(4,2)意思是 4 ∗ 4 4*4 4∗4。
最后 Q u i c k P o w ( 16 , 1 ) QuickPow(16,1) QuickPow(16,1)的意思是到此为止。因为第二个参数是1。

看到这里也许你可能还是一头雾水，下面请看这种说法：
例如： 3 ∗ 3 ∗ 3 ∗ 3 ∗ 3 ∗ 3 ∗ 3 ∗ 3 3*3*3*3*3*3*3*3 3∗3∗3∗3∗3∗3∗3∗3。（总共8个3）

我们这样计算（ 3 ∗ 3 ∗ 3 ∗ 3 ） ∗ 3 ∗ 3 ∗ 3 ∗ 3 （3*3*3*3）*3*3*3*3 （3∗3∗3∗3）∗3∗3∗3∗3先进行一个 3 ∗ 3 3*3 3∗3的运算。所以我们可以说上面的这个方程实际等价于（ 9 ∗ 9 ） ∗ 3 ∗ 3 ∗ 3 ∗ 3 （9*9）*3*3*3*3 （9∗9）∗3∗3∗3∗3。
最后通过递归到 ( 81 ) ∗ 3 ∗ 3 ∗ 3 ∗ 3 (81)*3*3*3*3 (81)∗3∗3∗3∗3知道81就是一个其中的一个解。然后前面是81，那么后面的 3 ∗ 3 ∗ 3 ∗ 3 3*3*3*3 3∗3∗3∗3也一定是81。所以最终81*81就是我们要的一个解。

再再看看下面这种说法：
Q u i c k P o w ( x , n ) QuickPow(x,n) QuickPow(x,n)的 n n n的意思是有几个 x x x需要相乘。如果 n = 1 n=1 n=1,那么就不需要继续进行相乘了。

小小的疑问：

那如果指数是奇数怎么办呢？
其实和偶数是一样的，奇书/2==偶数/2（“/”的意思是“整除”）。
我们只需要计算完结果然后像这样 x ∗ Q u i c k P o w ( x , n ) x*QuickPow(x,n) x∗QuickPow(x,n)手动的把 x x x多乘一份就可以了。

现在动手试一试吧，我想你一定能搞清楚递归函数是怎么样的。下面请看示例代码：

快速幂（递归）实现代码:

这里我为你准备了两个版本：
版本1：

#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
ll res = 1;
ll QuickPow(int x, int n) {
    if (n == 1)  //函数的退出条件
        return res *= x;

    if (n % 2 == 0) {  //偶数
        return QuickPow(x * x, n / 2);
    } else {  //基数
        return x * QuickPow(x * x, n / 2);
    }
}

int main() {
    cout << QuickPow(2, 3);
    return 0;
}

版本2：

#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
ll res = 1;
ll QuickPow(int x, int n) {
    if (n == 0)
        return 1;
    ll res = QuickPow(x * x, n / 2);
    if (n & 1)
        res = res * x;  //发现n是一个奇数，手动乘入x
}

int main() {
    cout << QuickPow(2, 3);
    return 0;
}

快速幂的设计思想2：

那么如果不用递归能不能实现快速幂呢？
答案当然是可以的。
我们设 n = 2 k n=2^k n=2k，为什么底数是 2 2 2呢？这个我们做一个悬念。
那么原来的方程： x n x^n xn可以写成 ( ( x 2 ) 2 ) 2 . . . ((x^2)^2)^2... ((x2)2)2...
只要进行k次那么答案就被我们求出来了。
又因为

所以计算机是2进制的世界，我们可以很轻松的操作二进制比如>>。所以将n转为2的倍数然后进而来表示n。
例如计算：

我们做一个16次的循环，不停的乘x，然后如果遇到指数是2，4，16（也就是22的二进制中10110为1的部分），就把他们乘入res中，最后就可以得到最终答案。这个方法的只要循环16次，比22次要少了很多。

快速幂（二进制）实现代码：

#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
ll QuickPow(int x, int n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1 == 1)
            res *= x;
        x *= x;
        n >>= 1;
    }
    return res;
}
int main() {
    cout << QuickPow(4, 9);
    return 0;
}

码农公寓

前言：