[数据结构与算法]c++ 算法--快速幂

快幂算法

我们先将b按2进制展开假设b = 10, 那么b的二进制为1010，也就是0*2^0+1*2^1+0*2^2+1*2^3 = 10；

所以 a^b = a^(0*2^0+1*2^1+0*2^2+1*2^3 ) = a^(2^1) * a(2^3)；这种简单的转换在初中就学过了吧，相信大家都懂

所以a^b%c = a^(2^1) * a(2^3) % c =( a^(2^1) % c) * (a(2^3)%c)%c；
?

#include<iostream>
#include<iomanip>
#include<algorithm>
#include<math.h>
 
using namespace std;
 
int qpow(int a, int b) //求a的b次方
{
	int ans = 1;
	while (b) 
	{	
		if (b & 1)//看b的末位是不是1, 也可以理解判断b奇偶数
		{
			ans *= a;
		}
		a *= a;//a自乘,下一次循环就会变成ans*=a^2, 依次类推
		b >>= 1;//踢掉末位
	}
	return ans;
}
 
 
int main() {
	long long a, b;
	cin >> a >> b;
	int ans;
	ans = qpow(a, b);
	return 0;
}