Stage 2 · Lesson 1 of 6
Modular arithmetic
When an answer is enormous, a problem asks for it modulo a number, usually 10^9 + 7 or . Modulo means the remainder after division. You may take the remainder after every addition, subtraction and multiplication and still get the right final remainder, which keeps every intermediate value small enough for a long long.
Multiplying two values below 10^9 + 7 fits in a long long, so multiply, then reduce. Subtraction needs care in C++, because the remainder of a negative number is negative: add the back. Division is different and needs a modular inverse, which comes later.
Common trapreducing only at the end, after an intermediate value has already overflowed.
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