用c++实现快速幂算法
时间: 2023-11-10 14:16:20 浏览: 58
快速幂算法(也称为二分幂算法)是一种在计算幂运算时,利用幂运算的特性,使得计算速度更快的算法。
C++代码实现如下:
```c++
#include<iostream>
using namespace std;
int pow(int a,int b,int mod)
//a是底数,b是指数,mod是模数
{
int res=1;
while(b>0)
{
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int main()
{
int a,b,mod;
cin>>a>>b>>mod;
cout<<pow(a,b,mod)<<endl;
return 0;
}
```
在该代码中,我们使用了位运算来加速计算,将指数 b 转化为二进制后,每次将 a 的平方乘到结果 res 中,并将 b 右移一位。当 b 的最低位为 1 时,将 a 乘到结果 res 中。
这样可以在 O(log b) 的时间复杂度内完成计算,比起普通的暴力求幂的时间复杂度 O(b) 要快得多。
相关问题
c++语言实现快速幂模算法
好的,下面是 C++ 实现快速幂模算法的代码:
```cpp
long long quick_pow_mod(long long a, long long b, long long m) {
long long ans = 1;
a %= m;
while (b) {
if (b & 1) ans = ans * a % m;
a = a * a % m;
b >>= 1;
}
return ans;
}
```
其中 `a` 表示底数,`b` 表示指数,`m` 表示模数。该函数返回的是 `a^b % m` 的值。
算法的思路是将指数 `b` 二进制拆分,每次将底数 `a` 自乘,如果当前二进制位是 1,则乘上当前底数,最后将结果对模数 `m` 取模得到结果。
这个算法可以用于解决一些数论问题,如求解离线查询的快速幂、快速幂求逆元等。
用c++实现一个快速幂代码
以下是使用C++实现快速幂的代码示例:
```c++
#include <iostream>
using namespace std;
// 计算 a^b 的值
int fastPow(int a, int b) {
int res = 1;
while (b > 0) {
if (b & 1) { // 判断 b 是否为奇数
res *= a;
}
a *= a; // a 每次平方
b >>= 1; // b 右移一位,相当于除以 2
}
return res;
}
int main() {
int a, b;
cin >> a >> b;
cout << fastPow(a, b) << endl;
return 0;
}
```
这里使用了位运算和循环来实现快速幂,可以将时间复杂度降为 O(log b)。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)