快速幂

题目大意

输入正整数\(a,b\)，输出\(a^b\)
其中，\(1\leq a,b \leq 1 \times 10^{9}\)
当然这个结果可能很大，要求你对结果取模1000000007(即\(10^{9}+7\))后输出

递归做法

#include
typedef long long ll;
const int mo=1e9+7;
int QuickPow(ll a,ll b){
	if(b==0)return 1; 
	a%=mo;
	ll ans;
	ll tmp=QuickPow(a,b>>1);
	if(b&1)ans=(tmp*tmp%mo)*a%mo;
	else ans=tmp*tmp%mo;
	return ans;
}
int main(){
	ll a,b;
	scanf("%lld%lld",&a,&b);
	printf("%lld",QuickPow(a,b));
}

非递归做法

#include
typedef long long ll;
const int mo=1e9+7;
int QuickPow(ll a,ll b){
	a%=mo;
	ll ans=1,tmp=a;
	while(b){
		if(b&1)ans=ans*a%mo;
		a=a*a%mo;
		b>>=1;
	}
	return ans;
}
int main(){
	ll a,b;
	scanf("%lld%lld",&a,&b);
	printf("%lld",QuickPow(a,b));
}