Modular Exponentiation

Problem Compute (a^b) mod c for large exponents b without overflow.

Input / Output

• Input: integers a, b (possibly up to 10^18), modulus c.
• Output: a^b mod c.

Constraints

• O(log b) required — naive repeated multiplication is O(b) and overflows anyway without per-step reduction.

Example

• a=2, b=10, c=1000 → 24; a=3, b=200, c=13 → 9.

Expected approach

• Binary exponentiation: result=1, base=a mod c; while b > 0: if b odd → result = result*base mod c; base = base² mod c; b >>= 1. Reduce mod c at EVERY multiplication — that's the overflow discipline being tested (and use a 128-bit/long-long intermediate if c² can overflow). O(log b). Extensions worth naming: recursive halving formulation, Fermat's little theorem for modular inverse when c is prime, matrix exponentiation reusing the same skeleton.