Modular arithmetic & fast power
Scenario
A problem asks you to calculate `(A^B) % M` where `A` and `B` can be up to 10^9. If you run a simple `for` loop to multiply `A` by itself `B` times, it will take 1 billion iterations and Time Limit Exceed (TLE).
How do you calculate massive powers in milliseconds instead of seconds?
Why it exists
Many combinatorial or graph problems have answers that grow exponentially (e.g., "How many ways to color a grid?"). To fit the answer in standard data types and test the algorithmic logic rather than BigInt implementation skills, problem setters require answers modulo a large prime (usually 10^9+7 or 998244353). Fast power allows calculating these massive combinatorial outcomes within the time limit. In real-world engineering, fast exponentiation is a foundational algorithm in cryptography, such as RSA encryption, which relies entirely on massive modular powers.
Mental model
Fast power (Binary Exponentiation) is like jumping across stepping stones by doubling your leap every time. Instead of taking 1,000 steps of size 1, you take steps of size 1, 2, 4, 8, 16... reaching your destination in roughly 10 leaps instead of 1,000.
Modular Arithmetic allows us to keep numbers small to prevent integer overflow while preserving mathematical correctness. Fast Power (Binary Exponentiation) is an O(log N) algorithm to calculate A^N % M by exploiting the binary representation of the exponent.
Explanation
**The Rules of Modular Arithmetic:**
In Competitive Programming (CP), answers can be massive. Problems will say "Output the answer modulo 10^9 + 7". To avoid overflow, you must apply the modulo operator `%` at every step, not just at the end. The core properties are:
- `(A + B) % M = (A % M + B % M) % M`
- `(A * B) % M = (A % M * B % M) % M`
- Subtraction requires caution: `(A - B) % M = (A % M - B % M + M) % M` (Adding `M` prevents negative results in C++).
**Modular Division:**
Modular arithmetic does not distribute over division. `(A / B) % M` is NOT `(A % M) / (B % M)`. Instead, you must multiply by the Modular Multiplicative Inverse (e.g., `A * B^(M-2) % M` if M is prime).
**Binary Exponentiation (Fast Power):**
Calculating 3^13 normally takes 13 multiplications. But 13 in binary is `1101` (8 + 4 + 1).
So, `3^13 = 3^8 * 3^4 * 3^1`.
We can compute `3^1, 3^2, 3^4, 3^8` by repeatedly squaring the base (`3^2 = 3*3`, `3^4 = 3^2 * 3^2`). We only multiply the result by the current base if the corresponding bit in the exponent is `1`.
This reduces the time complexity from O(N) to O(log N). For N = 10^18, a normal loop would take years; Fast Power takes about 60 iterations (microseconds).
Code examples
Iterative Fast Power
long long fast_power(long long base, long long exp, long long mod) {
long long res = 1;
base = base % mod; // Initial modulo just in case
while (exp > 0) {
// If the lowest bit is 1, multiply the result by the current base
if (exp % 2 == 1) {
res = (res * base) % mod;
}
// Square the base for the next bit
base = (base * base) % mod;
// Shift the exponent right by 1 bit
exp /= 2;
}
return res;
}This is the gold standard implementation. It uses bitwise logic (`exp % 2 == 1` is effectively `exp & 1`, and `exp /= 2` is `exp >>= 1`) to calculate massive powers in O(log(exp)) time while preventing overflow via the modulo.
Key points
- Modulo distributes over addition and multiplication: Apply `% M` at every single step, not just the end.
- Fast power is O(log N): Calculates A^B by repeatedly squaring the base and looking at the binary bits of the exponent.
Common mistakes
- Overflowing inside the modulo calculation: Even if you apply `% M` at every step, the intermediate calculation `(A * B)` might overflow a 32-bit `int` before the modulo is applied. If `M` is 10^9+7, `A*B` can be 10^18. You MUST use 64-bit integers (`long long`) for `res` and `base`.
Recall questions
- What is the time complexity of Binary Exponentiation?
- Why do we add `M` when performing modular subtraction: `(A - B + M) % M`?
- Why must you use 64-bit integers (`long long`) when calculating modulo arithmetic with M = 10^9 + 7?
Questions & answers
A developer attempts to compute `(A / B) % M` by doing `(A % M) / (B % M)`. This yields incorrect mathematical results. Why?
Modular arithmetic does not distribute over division. You cannot simply divide the remainders. You must multiply by the Modular Multiplicative Inverse of B (which is calculated using Fast Power as `B^(M-2) % M` if M is prime).
Approach: Recognize that division in modular arithmetic requires the concept of inverses.
When computing `(A - B) % M`, a developer writes `ans = (A % M - B % M) % M`. During testing, their program outputs a negative number, which fails the problem. How do you fix this?
In C++, the modulo operator on negative numbers preserves the negative sign. You must add `M` before the final modulo to wrap it back to the positive domain: `ans = (A % M - B % M + M) % M`.
Approach: Recognize language-specific implementations of the modulo operator on negative numbers.