1375. A Power of a Power, Modulo a Prime

Print a raised to the power b^c, reduced modulo a prime p.

a = 2, b = 2, c = 3, p = 1000000007 -> 2^8 = 256 a = 5, b = 0, c = 0, p = 7 -> 5^1 = 5 a = 5, b = 0, c = 3, p = 7 -> 5^0 = 1

Two conventions are settled here rather than left to taste, both matching problem 1372: x^0 is 1 for every x, including x = 0, and 0^0 is 1. So b = 0, c = 0 gives an exponent of 1, while b = 0, c > 0 gives an exponent of 0.

## What most people try first

Compute e = b^c, then call fast exponentiation on a^e. The first half is the problem. With b = 10^9 and c = 60 the exponent has about 540 decimal digits. No fixed width integer holds it, and reducing e modulo p is flatly wrong: exponents do not reduce modulo the modulus.

## Fermat reduces the exponent, modulo p-1

Fermat's little theorem says that if p is prime and a is not a multiple of p, then a^(p-1) ≡ 1 (mod p). So multiplying the exponent by a whole extra p-1 changes nothing, which means only the exponent's residue modulo p-1 matters:

a^E ≡ a^(E mod (p-1)) (mod p)

and E mod (p-1) is b^c mod (p-1), one ordinary fast power. So the answer is two fast powers, the first with modulus p-1 and the second with modulus p.

## Only when the modulus is prime, and only when a is not a multiple of it

Both conditions are load-bearing and both are tested.

• If p were composite, a^(p-1) need not be 1 at all and the reduction would
• simply be false. The correct general statement uses Euler's totient and an
• extra condition on the size of the exponent, which is why this problem pins
• p prime.
• If a is a multiple of p then a ≡ 0, the theorem does not apply, and the
• answer is 0 whenever the exponent is positive. Reducing the exponent could
• turn a positive exponent into 0 and print 1 instead, which is wrong. So
• that case is handled before any reduction happens.

A reduced exponent of 0 with a invertible needs no special case: a true exponent that is a multiple of p-1 gives 1 by Fermat, and a^0 is also 1, so both readings agree.

## Overflow

Inside each fast power the accumulator and the base are both below the modulus, which reaches 10^9 + 7, so every product reaches 10^18. A signed 64-bit integer holds that with room to spare; a 32-bit one stops at 2147483647. In JavaScript a plain Number is exact only below 2^53, so BigInt is required, and a itself reaches 10^18 so even reading it needs care.

## Cost

O(log c + log p) multiplications.

Constraints - `0 ≤ a ≤ 1000000000000000000` - `0 ≤ b ≤ 1000000000` - `0 ≤ c ≤ 60` - `2 ≤ p ≤ 1000000007`, and `p` is prime - `x^0` is `1` for every `x`, including `x = 0`