These are the notes for Competitive Programming episode 22 (number theory 4). Episode 21 showed that addition and multiplication survive "print the answer modulo 10^9 + 7", so we can take % M after every step and compute even 2^(10^18) with fast power. Today we hit the one operation that does not survive: division. In an original problem, Prize Split, the obvious power(2, k) / n gets Wrong Answer. A kirana shop calculator with a broken ÷ key leads to the modular inverse (the number that undoes multiplication), searching for it gets Time Limit Exceeded, and Fermat's little theorem turns the inverse into one call: power(n, M - 2), about 30 steps. A million-check stress test confirms it, and three real bugs close the episode. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
The real-life hooks
The kirana shop's broken ÷ key. A shopkeeper must split ₹1000 among 4 partners, but the ÷ key on his calculator is broken. He types 1000 × 0.25 instead and gets 250: the same answer with no division. It works because 4 × 0.25 = 1: multiplying by 0.25 undoes multiplying by 4. 0.25 is the inverse of 4. Mod world has no decimals, but it can still have undo numbers: modulo 7, 4 · 2 = 8, which leaves remainder 1, so 2 is the inverse of 4 (mod 7).
The seat shuffle. Six students sit in seats 1 to 6. The teacher says: "whoever is in seat k, move to seat 3 · k mod 7". Seat 1 → 3, 2 → 6, 3 → 2, 4 → 5, 5 → 1, 6 → 4. Nobody shares a seat and no seat is left empty: it is only a shuffle. That shuffle is the whole proof of Fermat's little theorem (below).
Recap: what survives mod M
- Modulo (
%):a % Mis the remainder when a is divided by M. 17 % 7 = 3. - Contest problems whose answers are huge ask for the answer modulo M, usually M = 10^9 + 7 (a prime that fits in an
int, and whose square fits in along long). - Addition survives:
(a + b) % M == (a % M + b % M) % M. - Multiplication survives:
(a · b) % M == (a % M) · (b % M) % M. - So we can take
% Mafter every single step, and numbers never grow past M. Fast power (binary exponentiation, episode 21) uses this to compute a^b % M in about log₂ b steps:
ll power(ll a, ll b) { // episode 21: a^b % M
ll r = 1;
for (a %= M; b > 0; b >>= 1, a = a * a % M)
if (b & 1) r = r * a % M;
return r;
}
- Division does not survive. That is today's problem.
Problem W · Prize Split
Problem W · Prize Split (written for this course). A quiz team of
nfriends wins 2^k rupees and splits it equally. For each ofqqueries (k,n), print one friend's share modulo M = 10^9 + 7. If the share is a fraction P / Q, print P · Q^(-1) mod M (it always exists here).
1 ≤ q ≤ 2·10^5,1 ≤ k ≤ 10^18,1 ≤ n ≤ 10^9. Time limit 2 seconds.
| Sample input | Sample output | Why |
|---|---|---|
310 4100 43 3 |
256494092823666666674 |
1024 / 4 = 256 · 2^100 / 4 = 2^98 ≡ 494092823 · 8 / 3 as a fraction mod M |
21 11000000000000000000 1000000000 |
240074821 |
2 / 1 = 2 · the largest k and n |
(The phrase "print P · Q^(-1) mod M" is explained below: it is exactly the modular inverse.)
The obvious attempt: divide after the mod (Wrong Answer)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll M = 1000000007;
ll power(ll a, ll b) { // episode 21: a^b % M
ll r = 1;
for (a %= M; b > 0; b >>= 1, a = a * a % M)
if (b & 1) r = r * a % M;
return r;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
ll k, n;
cin >> k >> n;
cout << power(2, k) / n << "\n";
}
return 0;
}
| Input | Output | Expected |
|---|---|---|
10 4 |
256 |
256 ✓ |
100 4 |
244092821 |
494092823 ✗ |
3 3 |
2 |
666666674 ✗ |
Why division breaks
Take a tiny modulus, 7:
- 12 / 4 = 3 (the true answer).
- 12 % 7 = 5, and 5 / 4 = 1 in integer division. Wrong.
Taking % 7 threw away a 7. The remainder 5 is not a multiple of 4 any more, so dividing it means nothing. Exactly the same happened to 2^100: 2^100 % M = 976371285, and 976371285 / 4 = 244092821 (rounded down), which has nothing to do with 2^98 % M.
And we cannot skip the mod: 2^(10^18) has about 3·10^17 digits. No computer can store it.
The modular inverse
The modular inverse of n (mod M), written n^(-1), is the number x in 1 … M − 1 with
n · x % M == 1
Dividing by n = multiplying by n^(-1). Check on the example that broke: 12 % 7 = 5; the inverse of 4 mod 7 is 2 (4 · 2 = 8 ≡ 1); 5 · 2 = 10, and 10 % 7 = 3. The right answer, from the remainder alone.
When does it exist? Only when n and M share no common factor, i.e. gcd(n, M) = 1 (episode 19). Mod 6, 2 has no inverse: 2 · x is always even, so 2 · x % 6 is 0, 2 or 4, never 1. That is why contests choose a prime M: then every n that is not a multiple of M has an inverse. If n can be a multiple of M, there is no inverse at all, just like dividing by zero.
Fractions mod M. 8 / 3 is not a whole number, so "8 / 3 mod M" means 8 · 3^(-1) mod M. 3^(-1) = 333333336 (3 · 333333336 = 1000000008 ≡ 1), so 8 / 3 ≡ 8 · 333333336 % M = 666666674. Check: 3 · 666666674 = 2000000022, and 2000000022 % M = 8. This is what "print P · Q^(-1) mod M" means, and you will see that sentence in hundreds of problems (probabilities, expected values, averages).
| n | n^(-1) mod 10^9 + 7 | check |
|---|---|---|
| 2 | 500000004 | 2 · 500000004 = 1000000008 ≡ 1 |
| 3 | 333333336 | 3 · 333333336 = 1000000008 ≡ 1 |
| 4 | 250000002 | 4 · 250000002 = 1000000008 ≡ 1 |
| 10 | 700000005 | 10 · 700000005 = 7000000050 ≡ 1 |
Brute force: search for the inverse (Time Limit Exceeded)
ll inverse(ll n) { // try x = 1, 2, 3 ...
for (ll x = 1; x < M; x++)
if (n % M * x % M == 1) return x;
return -1;
}
// in main: cout << power(2, k) * inverse(n) % M << "\n";
On the sample it prints the right answers, 256, 494092823, 666666674, but it already needs about a second: the inverse of 4 is 250000002, a quarter of a billion tries away. On a worst case of 2·10^5 queries with n near 10^9 (built inside main):
int main() {
int q = 200000; // worst case, built here
ll total = 0;
while (q--) {
ll n = 1000000000 - q;
total = (total + inverse(n)) % M;
}
cout << total << "\n";
return 0;
}
Result: Time Limit Exceeded (still running after 8 seconds). Each search can take up to M ≈ 10^9 steps; 2·10^5 of them is about 2·10^14.
Fermat's little theorem
Look for a pattern. Modulo 7, keep multiplying:
| a | a^1 | a^2 | a^3 | a^4 | a^5 | a^6 |
|---|---|---|---|---|---|---|
| 3 | 3 | 2 | 6 | 4 | 5 | 1 |
| 2 | 2 | 4 | 1 | 2 | 4 | 1 |
Every a from 1 to 6 gives a^6 ≡ 1 (mod 7), and 6 = 7 − 1. This is Fermat's little theorem (Pierre de Fermat, around 1640):
If p is prime and a is not a multiple of p, then a^(p−1) ≡ 1 (mod p).
Peel one a off: a · a^(p−2) ≡ 1. So
a^(-1) ≡ a^(p−2) (mod p), and in code
inverse(n) = power(n, M - 2).
For 3 mod 7: 3^5 = 243 = 7 · 34 + 5, so 3^(-1) = 5, and 3 · 5 = 15 ≡ 1 ✓.
M − 2 is about 10^9, but fast power needs only about 30 squarings to get there: O(log M).
Why it works: the seat shuffle
Take p = 7, a = 3, and multiply each of 1 … 6 by 3, mod 7:
| k | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 3 · k mod 7 | 3 | 6 | 2 | 5 | 1 | 4 |
The second row is the same six numbers, shuffled. (Two seats can't collide: if 3i ≡ 3j then 7 divides 3(i − j), and since 7 is prime and doesn't divide 3, it divides i − j, so i = j.) So the products of the two rows are equal mod 7:
3^6 · (1 · 2 · … · 6) ≡ 1 · 2 · … · 6 (mod 7)
1 · 2 · … · 6 has no factor 7, so it has an inverse and we can cancel it: 3^6 ≡ 1. The same argument works for any prime p and any a not divisible by p. It also shows why p must be prime: with a non-prime modulus, some seats can collide.
The accepted solution
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll M = 1000000007;
ll power(ll a, ll b) { // episode 21: a^b % M
ll r = 1;
for (a %= M; b > 0; b >>= 1, a = a * a % M)
if (b & 1) r = r * a % M;
return r;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
ll k, n;
cin >> k >> n;
cout << power(2, k) * power(n, M - 2) % M << "\n";
}
return 0;
}
| Input | Output |
|---|---|
3 / 10 4 / 100 4 / 3 3 |
256 / 494092823 / 666666674 |
2 / 1 1 / 1000000000000000000 1000000000 |
2 / 40074821 |
| 2·10^5 random queries | about 0.2 s |
power(2, k) * power(n, M - 2) multiplies two numbers below M ≈ 10^9: at most about 10^18, which fits in a long long (max ≈ 9.2·10^18). Then % M brings it back down.
A million-check stress test
A stress test checks a solution against something we trust, on many random inputs. Here the trusted fact is the definition itself: n · n^(-1) % M must be 1.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll M = 1000000007;
ll power(ll a, ll b) { // episode 21: a^b % M
ll r = 1;
for (a %= M; b > 0; b >>= 1, a = a * a % M)
if (b & 1) r = r * a % M;
return r;
}
int main() {
mt19937 rng(22);
int ok = 0;
for (int t = 0; t < 1000000; t++) {
ll n = rng() % (M - 1) + 1; // 1 .. M-1
if (n * power(n, M - 2) % M == 1) ok++;
}
cout << ok << " / 1000000 checks passed\n";
return 0;
}
Output: 1000000 / 1000000 checks passed (about 0.15 s). mt19937 is C++'s fast Mersenne Twister random number generator; the seed 22 makes every run produce the same numbers, so a failure can be reproduced.
Bonus: all inverses 1 … n in O(n)
When you need the inverse of every number from 1 to n (n up to 10^7), there is a linear-time recurrence. Write M = (M / i) · i + (M % i). Mod M the left side is 0, so (M / i) · i ≡ −(M % i). Multiply both sides by i^(-1) · (M % i)^(-1):
i^(-1) ≡ −(M / i) · (M % i)^(-1) (mod M)
M % i < i, so (M % i)^(-1) is already in the table:
vector<ll> inv(n + 1);
inv[1] = 1;
for (int i = 2; i <= n; i++)
inv[i] = (M - M / i) * inv[M % i] % M;
Checked against power(i, M - 2) for every i ≤ 10^6: 0 mismatches (inv[2] = 500000004, inv[10] = 700000005). For n = 10^7 it took about 0.45 s on our test machine, against about 2.2 s for 10^7 separate Fermat calls. Episode 23 uses a related trick for the inverses of factorials.
Complexity vs the constraints
| Approach | Time per query | Worst case here (q = 2·10^5) | Verdict |
|---|---|---|---|
power(2, k) / n |
O(log k) | fast | Wrong Answer |
| Search x = 1, 2, … | O(M) | up to 2·10^5 · 10^9 = 2·10^14 | TLE |
Fermat: power(n, M - 2) |
O(log k + log M) ≈ 60 + 30 | ≈ 2·10^7 steps | Accepted, ≈ 0.2 s |
| Inverse table 1 … n | O(1) after O(n) build | n ≤ 10^7 | when you need all of them |
Common mistakes (and the real outputs)
Bug 1: int inside the power function
int power(int a, int b) { // episode 21: a^b % M
int r = 1;
for (a %= M; b > 0; b >>= 1, a = a * a % M)
if (b & 1) r = r * a % M;
return r;
}
On the sample the program prints 0, 0, 381855169 instead of 256, 494092823, 666666674, with no error message. a · a can be close to 10^18, but an int holds at most 2147483647: the product overflows (wraps around; in C++ signed overflow is even undefined behaviour) before % M runs. Fix: long long for every value that gets multiplied.
Bug 2: a modulus that isn't prime
const ll M = 1000000000; // typo: 10^9, not 10^9 + 7
The stress test prints 0 / 1000000 checks passed. 10^9 = 2^9 · 5^9 is not prime, so Fermat's theorem does not apply, and even numbers (and multiples of 5) have no inverse at all. Fix: const ll M = 1000000007; (or the other common contest prime, 998244353). Copy the modulus from the statement; never retype it.
Bug 3: forgetting the last % M
cout << power(2, k) * power(n, M - 2) << "\n";
Output: 256000002048, 244092823202742570, 2666666688. The first is 256 + 256 · M: the right remainder, never reduced. The judge compares text, so this is Wrong Answer. Fix: % M after every multiplication.
Summary table
| Mistake | What you see | Why | Fix |
|---|---|---|---|
power(2, k) / n |
244092821 (expected 494092823) |
% threw away multiples of M |
* power(n, M - 2) % M |
int power(int a, int b) |
0 0 381855169, no error |
a · a overflows int |
long long everywhere |
const ll M = 1000000000; |
0 / 1000000 checks passed |
10^9 is not prime | M = 1000000007 |
x * power(n, M - 2) with no % M |
256000002048 (expected 256) |
product never reduced | % M after every × |
| inverse of a multiple of M | power(M, M - 2) returns 0, silently |
no inverse exists (like ÷ 0) | check the constraints |
| searching x = 1, 2, … | Time Limit Exceeded | up to 10^9 tries per query | Fermat |
Mini project
Build a reusable Mint (modular integer) helper: a struct holding a value in 0 … M − 1 with +, −, · (all reducing mod M, with the negative fix from episode 21), pow(b), inv() (Fermat) and / (multiply by inv()). Stress-test it: for a million random pairs (a, b) with b ≠ 0, check that (a / b) * b == a, and that a.inv().inv() == a. Then rewrite Problem W in three lines using it.
Practice
These follow the video's homework.
-
Print the average of n numbers (each ≤ 10^9) modulo 10^9 + 7.
Answer
Average = (sum) / n = (sum % M) · power(n, M − 2) % M. The sum can be reduced as you add. Results from running it: <code>1 2 4</code> → 7 / 3 → <code>333333338</code>; <code>5 10</code> → 15 / 2 → <code>500000011</code> (= 7 + 2^(-1), since 7.5 = 7 + 1/2). -
Compute the inverses of all numbers 1 … n (n ≤ 10^7) in O(n).
Answer
The recurrence from the bonus section: <code>inv[1] = 1; inv[i] = (M - M / i) * inv[M % i] % M</code>. Checked against Fermat for every i ≤ 10^6 (0 mismatches). <code>inv[2] = 500000004</code>, <code>inv[10] = 700000005</code>. -
Print 1 + 2 + … + n modulo M, for n ≤ 10^18.
Answer
The formula n(n + 1) / 2, with division by 2 done as multiplication by 2^(-1) = 500000004: <code>n % M * ((n + 1) % M) % M * 500000004 % M</code>. Reduce n first, or n · (n + 1) overflows. n = 10 → <code>55</code>; n = 10^18 → <code>1225</code> (because 10^18 ≡ 49 mod M, and 49 · 50 / 2 = 1225). -
The expected value of one roll of a fair six-sided die, as a fraction mod M.
Answer
(1 + 2 + 3 + 4 + 5 + 6) / 6 = 21 / 6 = 7 / 2. Both give the same residue: 21 · 6^(-1) ≡ 7 · 2^(-1) ≡ <code>500000007</code>. (A fraction has one value mod M, however you write it.) -
Without code: what is the inverse of 10 modulo 7? And why does 6 have no inverse modulo 9?
Answer
10 ≡ 3 (mod 7), and 3 · 5 = 15 ≡ 1, so 10^(-1) ≡ 5 (Fermat agrees: 10^5 % 7 = 5). 6 and 9 share the factor 3, so 6 · x is always a multiple of 3 and can never leave remainder 1 mod 9.
Quick quiz
11 is prime. What is power(3, 11 - 2), i.e. 3^9 % 11?
A) 1 · B) 4 · C) 3 · D) 9
Answer
B. By Fermat, 3^9 is the inverse of 3 mod 11, and 3 · 4 = 12 ≡ 1. Directly: 3^9 = 19683 = 11 · 1789 + 4. A would be 3^10 (= 3^(p−1)).
Interview questions
- Why can't you divide remainders directly? Taking
% Mthrows away multiples of M, so the remainder need not be divisible by n any more: 12 / 4 = 3 but (12 % 7) / 4 = 1. - What is a modular inverse, and when does it exist? The x with n · x ≡ 1 (mod M); it exists exactly when gcd(n, M) = 1.
- State Fermat's little theorem and how it gives the inverse. For prime p and a not divisible by p, a^(p−1) ≡ 1 (mod p); so a^(p−2) is a's inverse, computed with fast power in O(log p).
- Why do contests use 10^9 + 7? It is prime (so every non-multiple has an inverse), fits in a 32-bit
int, and the product of two residues (< 1.0·10^18) fits in a 64-bitlong long. - What if the modulus is not prime? Fermat fails. Use the extended Euclidean algorithm (episode 25), which finds the inverse whenever gcd(n, M) = 1, or Euler's theorem (episode 27).
- How do you compute many inverses quickly? The O(n) recurrence
inv[i] = (M - M / i) * inv[M % i] % M, or (for factorials) one Fermat call plus a backward pass (episode 23).
Glossary
| Term | Meaning | Example |
|---|---|---|
Modulo (%) |
The remainder after division | 17 % 7 = 3 |
| M = 10^9 + 7 | The usual contest modulus, a prime | const ll M = 1000000007; |
| Congruent (≡) | Same remainder mod M | 8 ≡ 1 (mod 7) |
| Fast power (binary exponentiation) | a^b % M in O(log b) by repeated squaring | power(2, 100) in 7 squarings |
| Modular inverse (n^(-1)) | The x with n · x ≡ 1 (mod M) | 4^(-1) ≡ 2 (mod 7) |
| Modular division | Multiply by the inverse instead of dividing | 12 / 4 ≡ 5 · 2 ≡ 3 (mod 7) |
| gcd | Greatest common divisor (episode 19) | gcd(6, 9) = 3, so 6 has no inverse mod 9 |
| Prime | A number with exactly two divisors | 7, 11, 10^9 + 7 |
| Fermat's little theorem | p prime, p ∤ a ⇒ a^(p−1) ≡ 1 (mod p) | 3^6 ≡ 1 (mod 7) |
| P · Q^(-1) mod M | How a fraction P / Q is printed in contests | 8 / 3 → 666666674 |
| Integer overflow | A value too big for its type wraps around | a · a in an int |
| Undefined behaviour | C++ makes no promise what happens (e.g. signed overflow) | 0 0 381855169 |
| Stress test | Check a solution on many random inputs against something trusted | 1000000 / 1000000 checks passed |
mt19937 |
C++'s Mersenne Twister random generator | mt19937 rng(22); |
| Seed | The starting value of a random generator; same seed, same numbers | 22 |
| Inverse table | All inverses 1 … n in O(n) | inv[i] = (M - M / i) * inv[M % i] % M |
Summary
+and×survive% M; division does not:(a % M) / ngives Wrong Answer (244092821instead of494092823).- Dividing by n is multiplying by its modular inverse, the x with n · x ≡ 1. It exists when gcd(n, M) = 1; for a prime M, whenever n isn't a multiple of M.
- Searching for x one by one is O(M) per query: TLE.
- Fermat's little theorem: a^(p−1) ≡ 1 mod a prime p, so
inverse(n) = power(n, M - 2), O(log M), about 30 steps. Proof: multiplying 1 … p − 1 by a only shuffles them. - Fractions are printed as P · Q^(-1) mod M (8 / 3 →
666666674). - Real bugs:
intin power (0 0 381855169), a non-prime M (0 / 1000000 checks passed), a missing final% M(256000002048).
Solutions in C++, Java and Python
Problem W · Prize Split
C++: the accepted program above.
Java (tested: the sample gives 256, 494092823, 666666674; the edge input gives 2, 40074821; 2·10^5 random queries gave output identical to C++ in about 0.6 s). BufferedReader and one StringBuilder keep the I/O fast.
import java.io.*;
import java.util.*;
public class Main {
static final long M = 1_000_000_007L;
static long power(long a, long b) { // a^b % M
long r = 1;
for (a %= M; b > 0; b >>= 1, a = a * a % M)
if ((b & 1) == 1) r = r * a % M;
return r;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int q = Integer.parseInt(br.readLine().trim());
StringBuilder sb = new StringBuilder();
while (q-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
long k = Long.parseLong(st.nextToken());
long n = Long.parseLong(st.nextToken());
sb.append(power(2, k) * power(n, M - 2) % M).append('\n');
}
System.out.print(sb);
}
}
Python (tested on the same inputs, same outputs; 2·10^5 random queries in about 1.4 s). Python's built-in three-argument pow(base, exp, mod) is fast power, and Python integers never overflow. Since Python 3.8, pow(n, -1, M) also returns the inverse directly.
import sys
M = 10**9 + 7
def main():
data = sys.stdin.buffer.read().split()
q = int(data[0])
out = []
for i in range(q):
k, n = int(data[1 + 2 * i]), int(data[2 + 2 * i])
# pow(base, exp, mod) is Python's built-in fast power
out.append(pow(2, k, M) * pow(n, M - 2, M) % M)
print("\n".join(map(str, out)))
main()