Modular Power — Solution & Editorial

Back to the Problem

Binary exponentiation: square the base and halve the exponent, multiplying the result in when the current bit is set. Reduce modulo M at every step.

Complexity: O(log B)

Watch out: B does not fit in 32 bits, and naive repeated multiplication is hopeless — exponentiate by squaring. Note 0⁰ is defined as 1 here.