Stage 2 · Lesson 5 of 6
Fast exponentiation
Computing a^e by multiplying e times is far too slow when e is 10^18. squares the base and multiplies it into the result whenever the current bit of e is set, so it needs only about log2(e) steps, around 60 for 10^18. Under a , reduce after every multiplication.
You will use it directly, for problems asking for a huge power, and indirectly, because modular inverses and many counting formulas are built on it. Learn to write it from memory in under a minute.
Common trapforgetting to reduce the base modulo m before the loop, so the first squaring overflows when the base itself is near 10^18.
A question to check yourself, an AI practice session and 1 cheat sheet entry come with the full roadmap. Unlock
Resources for this stage
Start with
- BookFreeCompetitive Programmer's Handbook
Antti Laaksonen · Beginner
Section 1.5 covers the maths basics and Chapter 21 covers number theory, from primes to modular inverses