Number Theory Practice Test: Sieve, Modpow and nCr Quiz
A timed 45-minute number theory practice test: the sieve, exponentiation by squaring, Fermat inverses, nCr mod p and 128-bit products for moduli near 10^18.
- Course: Competitive Programming study plan
- Module: Number theory: sieve, modular arithmetic, nCr
- Kind: Checkpoint — cleared at 70%
- Reading time: 45 min
- Runtime: Clang 18 · C++20
Checkpoint — Number theory is the checkpoint that closes the Number theory: sieve, modular arithmetic, nCr module: a graded quiz and whole-program exercises, passed at 70%.
Instructions
A timed checkpoint on contest number theory: the sieve and prefix counts, exponentiation by squaring, inverses under a prime modulus, factorial tables for nCr, and keeping every product inside its type.
How it works. Ten questions and one program, in 45 minutes from when you start the timer. Clear 70% of the questions and get the program accepted on every hidden case — moduli up to 10¹⁸ included — to complete the module.
Before you start, make sure you can answer these from memory:
- Why the sieve starts at p², and its complexity.
- The modpow loop, and why the result starts at
1 % m. - Why reduced residues below 1e9+7 multiply safely in
long long, and what changes near 10¹⁸. - How one modpow and two loops give every inverse factorial up to N.
- When an inverse exists modulo a composite number.
Common questions
How do you compute a^b mod m when a, b and m are up to 10^18?
Use exponentiation by squaring, about 60 steps for a 60-bit exponent, and do every multiplication in __int128: (__int128)x * y % m. Two residues below 10^18 multiply to up to 10^36, which overflows long long. Start the result at 1 % m so that m = 1 gives 0.
When does a modular inverse exist?
An inverse of b modulo m exists exactly when gcd(b, m) = 1. For a prime modulus such as 1e9+7 that is every b not divisible by it, and Fermat's little theorem gives it as b^(m-2) mod m; for a composite modulus use the extended Euclidean algorithm.
Exercise
Huge powers, huge modulus
Answer q questions: print a^b mod m. Take 0^0 = 1, so a^0 mod m is 1 mod m.
Input: q (1 ≤ q ≤ 10^4), then q lines a b m (0 ≤ a, b ≤ 10^18, 1 ≤ m ≤ 10^18). Output: one line per question.
5
2 10 1000
3 13 1000
5 0 7
7 3 1
0 0 10prints
24
323
1
0
1With m near 10¹⁸, the product of two residues reaches 10³⁶ — no 64-bit type holds it.
In this module: Number theory: sieve, modular arithmetic, nCr
← The sieve, modular arithmetic and nCr mod p · Disjoint set union — union by size and path compression →