06 Number theory: sieve, modular arithmetic, nCr / Lesson 1 of 1

The sieve, modular arithmetic and nCr mod p

Q: How do you compute nCr modulo 1e9+7?

Precompute factorials fact[i] = i! mod p up to the largest n, then inverse factorials: inv[n] = fact[n]^(p-2) mod p by Fermat's little theorem and inv[i-1] = inv[i] i mod p going down. Then C(n, r) = fact[n] inv[r] % p * inv[n-r] % p answers each query in O(1), and 0 when r > n. This works because 1e9+7 is prime.

15 min · +10 XP · 2 exercises · 4 questions

Read the text15 min

Exercises0/2

Quiz4 q

Quick answer

How do you compute nCr modulo 1e9+7?

Precompute factorials fact[i] = i! mod p up to the largest n, then inverse factorials: inv[n] = fact[n]^(p-2) mod p by Fermat's little theorem and inv[i-1] = inv[i] * i mod p going down. Then C(n, r) = fact[n] * inv[r] % p * inv[n-r] % p answers each query in O(1), and 0 when r > n. This works because 1e9+7 is prime.

Three tools cover most of the number theory a contest asks for: a sieve for every prime at once, modular exponentiation for huge powers, and factorial tables for binomial coefficients under a prime modulus.

The sieve

Testing each number by trial division costs O(n√n). The Sieve of Eratosthenes marks every composite up to n in O(n log log n): each prime crosses out its multiples, starting at its square.

The Sieve of Eratosthenes on 1..30

n = 30

Write 1 to 30. 1 is not prime; every other number starts unmarked. The first unmarked number is the next prime.

0:01 / 0:19Step 1 of 5

Transcript · 5 steps

vector<bool> composite(N + 1);
composite[0] = composite[1] = true;
for (ll p = 2; p * p <= N; ++p)
    if (!composite[p])
        for (ll m = p * p; m <= N; m += p) composite[m] = true;

Range questions — "how many primes in [l, r]" — become a prefix count over the sieve: O(1) each.
Keep the smallest prime factor instead of a bool and you can factor any number up to N in O(log N).

Powers by squaring

a^e mod m with e up to 10¹⁸ needs about 60 steps, not 10¹⁸.

Modular exponentiation by squaring

3^13 mod 1000

3^13 mod 1000 without 13 multiplications. 13 in binary is 1101, so 3^13 = 3^1 · 3^4 · 3^8. Start with result 1 and base 3.

0:01 / 0:18Step 1 of 6

Transcript · 6 steps

ll power(ll b, ll e, ll m) {
    ll r = 1 % m;
    b %= m;
    for (; e > 0; e >>= 1, b = b * b % m)
        if (e & 1) r = r * b % m;
    return r;
}

Reduce after every product. Below MOD = 1e9+7 two values multiply to under 2⁶⁰, safe in long long.
A modulus near 10¹⁸? Multiply in __int128: (__int128)a * b % m.
1 % m, not 1: when m = 1 the answer is 0.

Division mod a prime, and nCr

You cannot divide under a modulus, but you can multiply by an inverse. For a prime p, Fermat gives a⁻¹ = a^(p−2) mod p.

fact[0] = 1;
for (int i = 1; i <= N; ++i) fact[i] = fact[i - 1] * i % MOD;
inv[N] = power(fact[N], MOD - 2, MOD);
for (int i = N; i > 0; --i) inv[i - 1] = inv[i] * i % MOD;
// C(n, r) = fact[n] * inv[r] % MOD * inv[n - r] % MOD, and 0 when r > n

One modpow and two O(N) loops, then every query is O(1).

The traps

Three factors, one reduction. a * b * c % MOD overflows even when each is reduced; reduce after every product.
Negative results. (a - b) % MOD can be negative in C++; write (a - b + MOD) % MOD.
A composite modulus. Fermat's inverse needs a prime. Modulo a composite m, b has an inverse only when gcd(b, m) = 1.
Tables too small. Size them by the largest n any query can ask, not the first one you read.

More practice

Count Primes — the sieve itself.
Closest Prime Numbers in Range — sieve, then scan.
Count Good Numbers — modpow with a huge exponent.
Prime Arrangements — a sieve and factorials mod p.
Count Anagrams — multinomials with inverse factorials.

Common questions

What is the time complexity of the Sieve of Eratosthenes?

O(n log log n) time and O(n) memory. Each prime p crosses out about n/p numbers starting from p squared, and the sum of n/p over primes up to n grows like n log log n. A sieve up to 10^7 runs in well under a second.

Why is 1e9+7 used as a modulus?

It is prime, so every non-zero value has a modular inverse and division works through Fermat's little theorem. It is also below 2^30, so two reduced values multiply to less than 2^60 and fit in a long long without overflow.

How does fast modular exponentiation work?

Read the exponent's bits from the lowest. Each step squares the base, and multiplies the base into the result when the bit is 1, reducing modulo m every time. That takes O(log e) multiplications instead of e.

How do I multiply two numbers modulo m when m is near 10^18?

The product of two values below 10^18 can reach 10^36, far past long long. Cast to __int128 for the multiplication, (__int128)a * b % m, then back to long long. With a modulus below about 3·10^9 a plain long long product is enough.

Why does the sieve start crossing out at p squared?

Every smaller multiple k·p with k < p has a prime factor smaller than p, so an earlier prime has already crossed it out. Starting at p·p skips that repeated work and lets the outer loop stop once p·p exceeds n.

Mark as readSign in to keep your place.

Sieve of Eratosthenes, Modpow and nCr mod p in C++

The number theory contests use most: a sieve for primes up to 10^7, fast modular exponentiation, inverses by Fermat, and nCr mod 1e9+7 from factorial tables.

Course: Competitive Programming study plan
Module: Number theory: sieve, modular arithmetic, nCr
Kind: Lesson
Reading time: 15 min
Runtime: Clang 18 · C++20

How do you compute nCr modulo 1e9+7?

Lesson

The sieve

Testing each number by trial division costs O(n√n). The Sieve of Eratosthenes marks every composite up to n in O(n log log n): each prime crosses out its multiples, starting at its square.

The Sieve of Eratosthenes on 1..30. Example: n = 30

Write 1 to 30. 1 is not prime; every other number starts unmarked. The first unmarked number is the next prime.
2 is unmarked, so it is prime. Cross out its multiples from 4 = 2×2: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30. Smaller multiples of 2 have a smaller prime factor and are gone already.
3 is unmarked, so it is prime. Cross out its multiples from 9 = 3×3: 9, 15, 21, 27 (4 already crossed by a smaller prime). Smaller multiples of 3 have a smaller prime factor and are gone already.
5 is unmarked, so it is prime. Cross out its multiples from 25 = 5×5: 25 (1 already crossed by a smaller prime). Smaller multiples of 5 have a smaller prime factor and are gone already.
The next prime, 7, has 7² = 49 > 30: every composite up to 30 has a prime factor ≤ √30 and is crossed. The 10 numbers left are the primes. In all, O(n log log n).

vector<bool> composite(N + 1);
composite[0] = composite[1] = true;
for (ll p = 2; p * p <= N; ++p)
    if (!composite[p])
        for (ll m = p * p; m <= N; m += p) composite[m] = true;

Range questions — "how many primes in [l, r]" — become a prefix count over the sieve: O(1) each.
Keep the smallest prime factor instead of a bool and you can factor any number up to N in O(log N).

Powers by squaring

a^e mod m with e up to 10¹⁸ needs about 60 steps, not 10¹⁸.

Modular exponentiation by squaring. Example: 3^13 mod 1000

3^13 mod 1000 without 13 multiplications. 13 in binary is 1101, so 3^13 = 3^1 · 3^4 · 3^8. Start with result 1 and base 3.
Lowest bit of 1101 is 1: multiply the result by the base, 1 · 3 mod 1000 = 3. Then square the base (9) and shift the exponent right.
Lowest bit of 110 is 0: the result stays 3. Square the base to 81 and shift the exponent right.
Lowest bit of 11 is 1: multiply the result by the base, 3 · 81 mod 1000 = 243. Then square the base (561) and shift the exponent right.
Lowest bit of 1 is 1: multiply the result by the base, 243 · 561 mod 1000 = 323. Then square the base (721) and shift the exponent right.
The exponent is 0: 3^13 mod 1000 = 323, in 4 squarings, one per bit — O(log e). Reduce after every product, so each one is below 1000² and never overflows.

ll power(ll b, ll e, ll m) {
    ll r = 1 % m;
    b %= m;
    for (; e > 0; e >>= 1, b = b * b % m)
        if (e & 1) r = r * b % m;
    return r;
}

Reduce after every product. Below MOD = 1e9+7 two values multiply to under 2⁶⁰, safe in long long.
A modulus near 10¹⁸? Multiply in __int128: (__int128)a * b % m.
1 % m, not 1: when m = 1 the answer is 0.

Division mod a prime, and nCr

You cannot divide under a modulus, but you can multiply by an inverse. For a prime p, Fermat gives a⁻¹ = a^(p−2) mod p.

fact[0] = 1;
for (int i = 1; i <= N; ++i) fact[i] = fact[i - 1] * i % MOD;
inv[N] = power(fact[N], MOD - 2, MOD);
for (int i = N; i > 0; --i) inv[i - 1] = inv[i] * i % MOD;
// C(n, r) = fact[n] * inv[r] % MOD * inv[n - r] % MOD, and 0 when r > n

One modpow and two O(N) loops, then every query is O(1).

The traps

Three factors, one reduction. a * b * c % MOD overflows even when each is reduced; reduce after every product.
Negative results. (a - b) % MOD can be negative in C++; write (a - b + MOD) % MOD.
A composite modulus. Fermat's inverse needs a prime. Modulo a composite m, b has an inverse only when gcd(b, m) = 1.
Tables too small. Size them by the largest n any query can ask, not the first one you read.

More practice

Count Primes — the sieve itself.
Closest Prime Numbers in Range — sieve, then scan.
Count Good Numbers — modpow with a huge exponent.
Prime Arrangements — a sieve and factorials mod p.
Count Anagrams — multinomials with inverse factorials.

Common questions

What is the time complexity of the Sieve of Eratosthenes?

Why is 1e9+7 used as a modulus?

How does fast modular exponentiation work?

How do I multiply two numbers modulo m when m is near 10^18?

Why does the sieve start crossing out at p squared?

Exercises

Primes in ranges

Answer q questions: how many primes lie in the range [l, r], both ends included?

Input: q (1 ≤ q ≤ 10^5), then q lines l r (1 ≤ l ≤ r ≤ 10^6). Output: one line per question, the count.

prints

Trial division per question is far too slow at the limits; sieve once.

nCr modulo 1e9+7

Answer q questions: print C(n, r) — the number of ways to choose r items from n — modulo 1 000 000 007. When r > n the answer is 0.

Input: q (1 ≤ q ≤ 10^5), then q lines n r (0 ≤ n, r ≤ 10^6). Output: one line per question.

prints

Precompute factorials and inverse factorials up to 10⁶ once; each question is then O(1).

In this module: Number theory: sieve, modular arithmetic, nCr

← Checkpoint — Greedy algorithms and exchange proofs · Checkpoint — Number theory →