快速幂算法是一种用于快速计算幂运算（即 ab）的算法，其中 a 是底数，b 是指数。它的主要思想是减少乘法运算的次数，通过将指数 b 分解为二进制形式并利用幂的运算法则来加速计算过程。
以下是一个使用C++实现的快速幂算法的例子，它既可以处理正整数幂的情况，也可以稍微修改以处理模幂运算（即 abmodm）的情况：
普通快速幂算法（计算 ab）
#include <iostream> | |
using namespace std; | |
// 函数计算 a 的 b 次方 | |
long long fastPower(long long a, long long b) { | |
long long result = 1; // 初始化结果为1 | |
a = a % 1000000007; // 如果需要模运算，可以在这里加上取模操作 | |
while (b > 0) { | |
// 如果b是奇数，则乘以当前的a | |
if (b & 1) { | |
result = (result * a) % 1000000007; // 如果需要模运算 | |
} | |
// b右移一位（相当于b除以2），a平方 | |
b >>= 1; | |
a = (a * a) % 1000000007; // 如果需要模运算 | |
} | |
return result; | |
} | |
int main() { | |
long long a, b; | |
cout << "Enter base and exponent: "; | |
cin >> a >> b; | |
cout << "Result: " << fastPower(a, b) << endl; | |
return 0; | |
} |
注意：在上述代码中，我加入了取模操作（% 1000000007），这是为了防止结果溢出，并且在处理大数问题时非常有用。如果不需要取模，可以移除所有 % 1000000007 操作。
模幂运算（计算 abmodm）
上面的代码已经包括了模幂运算的示例，但是如果你想要一个更明确的函数来处理模幂运算，可以这样写：
long long modPower(long long a, long long b, long long m) { | |
long long result = 1; | |
a = a % m; // 先对a取模 | |
while (b > 0) { | |
if (b & 1) { | |
result = (result * a) % m; | |
} | |
b >>= 1; | |
a = (a * a) % m; | |
} | |
return result; | |
} |
这个函数接受三个参数：底数 a，指数 b，和模数 m，并返回 abmodm 的结果。这在密码学、大数运算等领域非常有用。