1069：乘方计算快速幂

1.快速幂

#include<bits/stdc++.h>
using namespace std;
int main()
{int a, n, r = 1;//r:结果cin>>a>>n;while(n){if(n & 1) r*=a;//如果b当前二进制为1就要乘上这个数n>>=1; //将b末尾的二进制数删掉a*=a;}cout<<r;return 0;}

2.循环
#include <bits/stdc++.h> using namespace std; int main() { int a, n, r = 1; cin>>a>>n; for(int i = 0; i < n; ++i) r *= a; cout<<r; return 0; }
3.pow函数
`#include<bits/stdc++.h>
using namespace std;
int main()
{
int a, n;
cin>>a>>n;
cout<<(int)pow(a, n);//cout直接输出浮点数相当于用printf以%g形式输出，当有效数字位数很多时会以科学计数法的形式输出。转为int型后就会直接输出数字。
return 0;
}

4.递归#include <bits/stdc++.h>
using namespace std;
int mi(int a, int n)
{
if(n == 0)
return 1;
else
return a * mi(a, n - 1);
}
int main()
{
int a, n, r = 1;
cin>>a>>n;
cout<<mi(a, n);
return 0;
}
`
快速幂算法，又称为快速指数算法，是一种优化的乘方计算方法。在传统的乘方计算中，如果我们要计算，通常需要进行次乘法操作。然而，快速幂算法通过将乘方数拆分并利用乘方的性质，减少了乘法操作的次数，从而达到加速计算的目的。
快速幂算法的核心在于指数的二进制分解。具体来说，算法将指数表示为二进制数，并利用幂的性质 以及 来分解乘方运算。通过这种方式，算法将原始的乘方问题转化为一系列的平方和乘法问题，显著减少了计算量。
首先假设我们要求5^13次方

13的二进制为1101 所以13 = 8+4+1；

即5^13 = 5^1 * 5^4 * 5^8