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.
asked …