C++利用快速幂算法实现函数long long quickPow(int n, int k),
时间: 2023-06-06 17:07:41 浏览: 78
非常高效的计算整数 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` 即可。
使用代码利用快速幂进行计算an。
好的,以下是在C++中使用快速幂算法计算a的n次幂的代码示例:
```cpp
#include <iostream>
using namespace std;
long long quickPow(long long a, long long n) {
if (n == 0) {
return 1;
}
long long t = quickPow(a, n / 2);
if (n % 2 == 0) {
return t * t;
} else {
return t * t * a;
}
}
int main() {
long long a, n;
cin >> a >> n;
long long res = quickPow(a, n);
cout << a << "的" << n << "次幂为:" << res << endl;
return 0;
}
```
在这个示例代码中,我们定义了一个函数quickPow来计算a的n次幂,然后在主函数中输入a和n,最后输出计算结果res。
相关推荐
![](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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)