~/problems
Problems
Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.
Modular arithmetic
Fast exponentiation, Fermat inverses, nCr mod p with factorial tables.
Notes
Recognise it when: the problem says "answer modulo 10^9 + 7", or it involves huge powers or counting.
pow(a, b, m)is built in. Know how to write it by hand: square-and-multiply over the bits of b.- Inverse modulo a prime p:
pow(a, p - 2, p)(Fermat). In Python 3.8+,pow(a, -1, m)works for any a coprime to m. - nCr mod p: precompute
factandinv_factup to n. ThenC = fact[n] * inv_fact[r] * inv_fact[n-r] % p. - Subtraction:
(a - b) % mis always non-negative in Python.
Gotchas: apply % m after every multiplication (in other languages that's overflow, in Python it's speed). Division needs the inverse.
7 problems
Advanced & competitive
Number theory Modular arithmetic, primes, matrix powers.
Modular arithmetic
- Basics: dividing under a prime modulus basics easy
- Yeast growth over a range of hours py · c++ · java easy
- Pow(x, n) py · c++ · java easy
- Power with a huge digit-list exponent py · c++ · java medium
- Modular exponentiation py · c++ · java easy
- nCr mod p for many queries py · c++ · java medium
- Inverse modulo a prime py · c++ · java easy