yukicoder : No.403 2^2^2

明日富士山に登るのでARCは不参加です。レートより低い標高から行きます。
http://yukicoder.me/problems/no/403

問題

３整数A,B,Cが与えられる。
(A^B)^CとA^(B^C)それぞれM=1000000007で割った余りを求めよ。

解法

前者は普通に(((A^B)%M)^C)%Mを答えるだけ。
後者はWriterのEditorialによるとこちらに答えがあるようだ。
よって(A^((B^C)%(M-1)))%Mを答えればよい。

1点注意点として、(B^C)%(M-1)==0の場合A^0だから解は1、と答えたくなるがそうではない。
A^(M-1)==1なのはあくまでAが非0の場合だけだし、B^Cは0にはなり得ないのでA%M==0の時は(B^C)%(M-1)==0であっても0と答えなければならない。

ll A,B,C;
ll mo=1000000007;

ll modpow(ll a, ll n,ll m) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%m,a=a*a%m,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%lld^%lld^%lld",&A,&B,&C);
	A%=mo;
	ll D=modpow(modpow(A,B,mo),C,mo);
	B%=mo-1;
	ll E=modpow(A,modpow(B,C,mo-1) + (mo-1),mo);
	
	cout<<D<<" "<<E<<endl;
	
	
}

まとめ

自分の書いたブログも結構覚えてないもんだ。