a的n次方

2022-12-30 14:05:21 第一文档网 [ 字体：小中大 ] [

阅读： ] [

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。下载word有问题请添加QQ：admin处理，感谢您的支持与谅解。

【#第一文档网# 导语】以下是®第一文档网的小编为您整理的《a的n次方》，欢迎阅读！

a的n次方

例子求43

3的二进制表示为11，即3=20+21； 43

=4^(20+21) =4^20*4^21 =41*42

话不多说，上代码：

#include using namespace std;

long long Mi(int a, long long n) {

long long ans = 1; long long tmp = a; while (n != 0){

if (n & 1 == 1) //二进制位运算，判断最后一位是否为1

ans = ans*tmp;

n = n >> 1; //二进制位运算，向右移动一位，即去掉最后一位

tmp = tmp*tmp; }

return ans; }

int main( {

cout << Mi(4, 3) << endl; system("pause"); return 0; }。

上述代码有几个缺点，比如a必须是整数、n必须是自然数（不能为负数）。

改进后总结

如果我们使用普通的方法（用for循环从1到n累乘），它的时间复杂度为O(n)。而使用上面的方法，它的时间复杂度为O(logn)。当n非常大时，采用上诉方法可以节省不少时间。

本文来源：https://www.dywdw.cn/4b85a842a11614791711cc7931b765ce04087a5a.html