2^2^2 [yukicoder 403]

問題

http://yukicoder.me/problems/no/403

自然数 A,B,C が与えられる。
(A^B)^CとA^(B^C)をそれぞれ出力せよ。

1 <= A,B,C <= 10^16

考察

1. (A^B)^C は高速累乗を使ってやれば普通にできる
2. A^(B^C)が問題
3. B^Cを先に計算する時に mod 10^9+7 で計算しても良いのかという問題
4. a = b (mod X) のときに A^a = A^b (mod X) であるとはいえない
5. フェルマーの小定理を知ってるかどうか

フェルマーの小定理
x^(p-1) = 1 (mod p)

6. ある素数を法として割り算をする時に普通は使う
7. これを利用すると a = b (mod X-1) のときに A^a = A^b (mod X) となる
8. これで計算すると答え

9. （本番は0の0乗が1で帰ってきてて落ちてた）

実装

http://yukicoder.me/submissions/106478

typedef long long ll;
ll modpow(ll a, ll n, ll MOD) {
	a %= MOD;
	if (a == 0) return 0;
	ll r = 1;
	while (n) r = r*((n % 2) ? a : 1) % MOD, a = a*a%MOD, n >>= 1;
	return r;
}
//-----------------------------------------------------------------
ll A, B, C;
ll mod = 1000000007;
ll solve1() {
	ll D = modpow(A, B, mod);
	return modpow(D, C, mod);
}
ll solve2() {
	ll D = modpow(B, C, mod - 1);
	return modpow(A, D, mod);
}
//-----------------------------------------------------------------
int main()
{
	scanf("%lld^%lld^%lld", &A, &B, &C);
	cout << solve1() << " " << solve2() << endl;
}