利用快速幂算法实现函数long long quickPow(int n, int k),
时间: 2023-06-06 09:07:44 浏览: 59
请问你知道如何实现吗?
好的,我可以回答这个问题。快速幂算法可以用于计算一个数的高次方,具体实现方式如下:
long long quickPow(int n, int k) {
long long res = 1;
while (k) {
if (k & 1) res *= n; // 当k的当前比特位为1时,将res乘以当前n的幂
n *= n; // n每次平方
k >>= 1; // k每次右移一位
}
return res;
}
这样就能快速地计算出n的k次方了。
相关问题
C++利用快速幂算法实现函数long long quickPow(int n, int k),
非常高效的计算整数 n 的 k 次幂,你能给出代码实现吗?
当然可以,以下是代码实现:
long long quickPow(int n, int k) {
long long ans = 1;
long long base = n;
while (k) {
if (k & 1) ans *= base;
base *= base;
k >>= 1;
}
return ans;
}
这个算法的思想是利用二进制分解来加速计算,将 k 在二进制下进行分解,在每一位上判断是否为 1,如果为 1 则将当前幂乘到答案上,然后将 base 进行平方,相当于将幂次加倍。这个算法的时间复杂度是 O(logk),非常高效。
利用快速幂进行计算a的n次方完整代码
下面是利用快速幂进行计算a的n次方的完整C++代码:
```c++
#include <iostream>
using namespace std;
long long power(long long a, long long n) {
long long res = 1;
while(n) {
if(n & 1) res *= a;
a *= a;
n >>= 1;
}
return res;
}
int main() {
long long a, n;
cin >> a >> n;
cout << power(a, n) << endl;
return 0;
}
```
其中 `power` 函数是快速幂算法的具体实现,`a` 表示底数,`n` 表示指数。在 `while` 循环中,如果当前 `n` 的二进制最低位为1,则将结果 `res` 乘上 `a`,同时将 `a` 自乘;否则,将 `a` 自乘即可。最后返回 `res` 即可。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.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)