快速幂算法C++

快速幂算法C++

• 一个简单例子快速了解
• 例题代码

一个简单例子快速了解

计算 2的13次方，首先，我们将指数13转换为二进制形式，得到1101。

然后，我们从右到左遍历每一位：

• 第一位是1，所以我们将结果乘以 2的2⁰次方=2的1次方=2；
• 第二位是0，所以我们不需要乘以任何东西；
• 第三位是1，所以我们将结果乘以 2的2²次方=2的4次方=16；
• 第四位是1，所以我们将结果乘以 2的2³次方=2的8次方=256。

所以，2的13次方=2×16×256=8192。

例题代码

求 2**2023%1000，即 2的2023次方除以1000的余数。
答案提交
　　这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

#include<iostream>
using namespace std;

int fastPower(int base, int power, int mod) {
    int result = 1;
    while (power > 0) {
        if (power & 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        power >>= 1;
    }
    return result;
}

int main() {
    cout << fastPower(2, 2023, 1000);
    return 0;
}

在上面的C++代码中，fastPower函数就是实现了这个算法。
　　它接受三个参数：基数base、指数power和模数mod。
　　在函数体中，它首先初始化结果result为1，然后进入一个循环，循环条件是power > 0。在每一轮循环中，它首先检查power的最低位是否为1，如果是，就将result乘以base并取模mod；然后，无论power的最低位是否为1，都将base自身平方并取模mod，并将power右移一位。这样，当power变为0时，循环结束，result就是2的2023次方对1000取余的结果。这就是快速幂算法的实现。