Handbooks / Data Structures & Algorithms / Chapter 10
Math and Number Theory
7 pages · ~5 min✓ Reviewed
Builds on Bit Manipulation.
Modulo and Overflow: The Mental Model
1. Definition and Safe Operations
a mod m= remainder in [0, m-1]a ≡ b (mod m)means m divides (a-b)- Reduce at every step:
(a*b) % m = ((a%m)*(b%m)) % m
| Op | Reduce each step? | Rule |
|---|---|---|
+ - * | Safe | reduce after each |
/ | Not allowed | (a/b)%m ≠ (a%m)/(b%m); use the modular inverse |
2. Negative Operands
cpp
int r = ((a % m) + m) % m;
C++/Java: -7 % 5 = -2; the fix gives 3
3. Overflow with 1e9+7
- a, b < 1e9+7prime modulus
- a*b ≈ 1e18too big for int
- long long64-bit
- % mafter each multiply