用c++实现一个快速幂
时间: 2023-12-03 20:49:28 浏览: 50
以下是C语言实现快速幂的代码:
```c
#include <stdio.h>
long long fast_pow(int base, int exponent) {
long long result = 1;
while (exponent > 0) {
if (exponent & 1) {
result *= base;
}
base *= base;
exponent >>= 1;
}
return result;
}
int main() {
int base = 2, exponent = 10;
long long result = fast_pow(base, exponent);
printf("%d^%d = %lld\n", base, exponent, result);
return 0;
}
```
该代码使用了位运算实现了快速幂算法,可以提高计算效率。在该算法中,我们使用了一个while循环,每次将指数折半,将底数平方,如果指数的二进制位为1,则将结果乘上底数。最后返回结果即可。
相关问题
用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)。
用c++实现快速幂算法
快速幂算法(也称为二分幂算法)是一种在计算幂运算时,利用幂运算的特性,使得计算速度更快的算法。
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) 要快得多。