快速幂

带模快速幂：

#include<iostream>
using namespace std;
#define ll long long
const int Mod = 100003;

ll quickPower(ll a,ll b){ //技巧：根据公式：a^b = a^(b/2)*a^(b/2) 进行分解 
	if( b==0 ){
		return 1;
	}
	ll re = quickPower(a,b/2)%Mod;
	if( b%2==0 ){
		return ((re%Mod)*re)%Mod;
	}
	else{
		return ((((re%Mod)*re)%Mod)*a)%Mod;
	}
} 

ll quickPower2(ll a,ll b){ //技巧：根据公式：a^b = (a^2)^(b/2) 进行分解 
	if( b==0 ){
		return 1;
	}
	if( b%2==0 ){ 
		return quickPower((a%Mod)*(a%Mod)%Mod,b/2);
	}
	else{
		return quickPower((a%Mod)*(a%Mod)%Mod,b/2)*(a%Mod)%Mod;
	}	
}

ll quickPower3(ll a,ll b){ //技巧：对指数b进行二进制拆分 
	ll ans = 1;
	ll k = a;
	while( b ){
		if( b&1 ){
			ans = ans*k%Mod;
		}
		k *= k;
		k%=Mod;
		b=b>>1;
	}
	return ans;
}

int main(){
	ll m,n;// m的n次方
	cin>>m>>n;
	cout << quickPower(m,n) ;
	return 0;
}