【学习笔记】快速幂

当学习并熟练掌握 $(a^n)^m=a^{n \times m}$ 后，我发现我原来想的好麻烦......

$a^b=(a^2)^{\tfrac{b}{2}}$

比如：计算$3^{10}$

$3^{10}=(3^2)^5=9^5=(9^2)^2 \times 9=81^2 \times 9=(81^2)^1 \times 9=6561^1 \times 9=59049$

主要思想就是计算 $a^b$ 时尽量让 $a$ 大，底数变大，指数变小，经过许多次这样的操作指数一定会变成 $1$。

也可以理解现在我们想求 $basic^{power}$，什么时候 $power=1$ 了，那就可以退出循环。

代码：

#include
#include
using namespace std;
long long result = 1;
long long basic;//底数
long long power;//指数
long long p;//模数 
int main(){
	cin >> basic >> power >> p; 
	printf("%Ld^%Ld mod %Ld=",basic,power,p);
	while(1){
		if(power == 1){
			result = result*basic;
			break;
		}
		if(power%2 == 0){
			power = power/2;
			basic = basic*basic %p;
		}
		else{
			power = power-1;
			result = result*basic %p;
			power = power/2 ;
			basic = basic*basic %p;
		}
	}
	cout << result%p << endl;
	
	return 0;
}

精简版：

long long fastPower(long long base,long long power,long long p){
	long long result = 1;
	while(power > 0){
		if(power & 1){
			result = result*base%p;
		}
		power >>= 1;
		base = (base*base)%p;
	}
	return result; 
}