快速幂
一、算法简介
快速幂也叫二分幂，用来快速求解：
朴素逐项累乘的时间复杂度为 ，当指数 极大时会超时。 快速幂基于二进制拆分思想，将时间复杂度优化为 。
二、原理推导
1. 指数二进制分解
设指数 的二进制展开为：
根据幂运算性质：
2. 递推关系
相邻幂次满足：
每次只需对当前底数平方，即可得到下一项。
3. 模运算性质
为避免溢出，运算全程取模，利用公式：
三、算法流程
- 初始化结果 ，当前底数 ；
- 依次取出 的每一个二进制位：
- 若当前二进制位为 ，执行 ；
- 更新底数：；
- 将 右移一位（去掉当前最低二进制位）；
- 遍历结束后， 即为答案。
四、代码实现
C++ 迭代版
#include <iostream>
using namespace std;
typedef long long ll;
ll qpow(ll a, ll b, ll mod)
{
ll res = 1;
a %= mod;
while (b)
{
if (b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int main()
{
ll a, b, m;
cin >> a >> b >> m;
cout << qpow(a, b, m) << endl;
return 0;
}
暂无评论