Power the Power Up

This post is in reference to SPOJ 21690. Power the Power Up POWERUP.

How do you solve a^{b^c} (mod m) where m is prime?

Reality check: you can’t just crunch the numbers since this might be 1111111111^1111111111^1111111111.

First, the highest part b^c must be chopped down. Fortunately our answer is taken modulo a prime number. So if we can solve for n where a^n = 1 (mod m), we can safely take b^c (mod n).

E.g. if a^n=1 (mod m), then {a^n} * {a^n} * ... = 1 (mod m); these n exponents disappear.

This is Fermat’s Little Theorem (a.k.a. phi function, totient), giving us n = phi(m) = m - 1 when m is prime.

So, calculate b^c(mod m-1) using modular exponentiation. Then do it again on a with (mod m). This operation is as follows:

typedef unsigned long long uint64;
uint64 modular_pow(uint64 base, uint64 exp, uint64 mod) {
	uint64 result = 1;
	base = base % mod;
	while (exp > 0) {
		if (exp % 2 == 1) {
			result *= base;
			result %= mod;
		}
		exp >>= 1;
		base *= base;
		base %= mod;
	}
	return result;
}

But wait! There’s one loose end: what if we can’t solve a^n = 1 (mod m)? This case too must be handled but I’ll leave that to you.