【模板】快速幂

快速幂|二进制取幂--$ Binary Exponentiation $

描述：

• 应用定理： (a^b+c=a^b+a^c,a^2b=a^b cdot a^b=(a^b)^2)。
• 时间复杂度： (mathbf{ heta}(log n)) 时间内算出 (a^n)。
• 思路：
  0.1将 (n) 转化为二进制位， (n=(n_tn_{t-1}...n_1n_0)_2)。
  0.2 (n) 有 (leftlfloorlog_2 n ight floor) 个进制位，所以我们算出 (a^1,a^2,a^4,a^8,...,a^{2^leftlfloorlog_2 n ight floor}) 后，计算 (mathbf{ heta}(log n)) 次乘法可计算出 (a^n)。
  0.3展开即为： $$n=n_tt^t+n_{t-1}t{t-1}+n_{t-2}t^{{t-2}+...+n_12}1+n_02^0$$
  0.4其中 (n_iin{0,1}) 那么就有 $$a^n=(a{n_t2^t+...+n_020})=a^{n_0 2^0} imes a^{n_1 2^1} imes ... imes a^{n_t 2^t}$$
  0.5即计算了 (mathbf{ heta}(log n)) 个 (2^k) 次幂的数，然后花费 (mathbf{ heta}(log n)) 的时间选择二进制为1对应的幂来相乘。

实现：

标准快速幂：

• 递归：

long long int binpow(long long int a,long long int b)
{
	if(b==0)return 1;
	long long int res=binpow(a,b/2);
	return b%2?res*res*a:res*res;
}

• 递推：

long long int binpow(long long int a,long long int b) {
	long long int res=1;
	while(b>0)
	{
		if(b&1)res=res*a;
		a=a*a,b>>=1;
	}
	return res;
}

取模快速幂：

long long int binpow_mod(long long int a,long long int b,long long int m)
{
	a%=m;
	long long int res=1%m;
	while(b>0)
	{
		if(b&1)res=res*a%m;
		a=a*a%m;
		b>>=1;
	}
	return res;
}