代码模板整理（3）：快速幂

严谨的代码模板整理

快速幂求的是什么
$$
求a^b \ mod\ p
$$
快速幂的范围可以到多少
$$
0\le a,b<2^{31},a+b>0,2\le p<2^{31}
$$
快速幂怎么求

​ 数学 $+$ 递归 $+$ 递推

快速幂的具体求法

首先，考虑到数据范围，我们采取 $unsigned$ $long$ $long$ 的类型存储数据

然后，考虑到$a$的指数$b$可以被二进制地拆分为$1,2,4,8...$这些数，分别对应了二进制中的各个权值

因此， 用一个$base$作为权值，用$b$&$1$来判断该二进制位上的数是否为$1$，然后计算乘积，最后$base$自我升华

代码如下

$A.\ a^b$

unsigned long long ksm(unsigned long long a,unsigned long long b) {
	unsigned long long ans=1,base=a;
	while(b>0) {
		if(b&1)ans*= base;
		base*=base;
		b>>=1;
	}
	return ans;
}

$B. \ a^b \ mod \ p$

unsigned long long ksm(unsigned long long a,unsigned long long b,unsigned long long p) {
	unsigned long long ans=1,base=a;
	while(b>0) {
		if(b&1)ans*= base;
		ans%=p;
		base*=base;
		base%=p;
		b>>=1;
		base%=p;
	}
	return ans;
}