快速幂学习笔记

快速幂学习笔记

啥是快速幂

快速幂，顾名思义，就是快速算某个数的多少次幂。其时间复杂度为 (O(log N))， 与朴素的(O(N))相比效率有了极大的提高。

原理

来自学长：

我们可以把 (b) 分解成二进制数，其中从小到大每一个二进制位
是 (b_1 ,b_2 ,...,b_{⌊log b+1⌋}) 。
根据二进制转十进制的原理，(b) 的十进制表示是可以通过
(b_1 ,b_2 ,...,b_{⌊log b+1⌋}) 的值在 (O(log n)) 的时间内解出的。
这就启发了我们可以用同样的方法去算 (a^b) 。

计算(a)的(b)次幂(a^b),如果(a)为偶数显然有(a^b=(a^{frac{b}{2}})^2)，也就是说我们仅需要计算其(b/2)幂，然后平方即可，如果n为奇数可以写成(a^b=a imes (a^{frac{b-1}{2}})^2)，该方法可以迭代的进行，大大降低了计算所需的时间。

由于算出的数可能特别大，所以通常会在计算过程中对一个数取模，保证了不会爆掉，这样的运算叫做快速幂取余运算

代码实现

代码实现比较简洁，用上位运算速度还会快些，写的时候最好都用long long来写，不然有可能爆(int)

#define ll long long
ll power(ll a,ll b,ll c){
	ll res=1;
	while(b){
		if(b&1)//判断二进制最后一位是否为1
			res=res*a%c;
		a=a*a%c;
		b>>=1;//每次除以2
	}
	return res%c;
}