Number Theory
Modular arithmetic: fast exponentiation, the modular inverse and C(n,k) modulo a prime.
Combinatorics answers are often astronomical, so problems ask for them "modulo 10⁹ + 7". You can work with remainders almost like with numbers:
• (a + b) % m, (a · b) % m — take the remainder after every operation;
• subtraction: ((a - b) % m + m) % m — to avoid going negative;
• there is NO division in modular arithmetic — instead, multiply by the modular inverse.
Fast exponentiation: a^b in O(log b) — square the base and walk the bits of the exponent. By Fermat's little theorem, for prime m the inverse is a⁻¹ = a^(m-2) — that same fast exponentiation.
C(n, k) modulo a prime via factorials and inverses. Enter: 10 3
Check: C(10, 3) = 120.
Breaking down binpow: while the exponent is non-zero, look at the lowest bit (b & 1): if the bit is set — multiply into the result; then square the base and shift the exponent (b >>= 1). For b = 10¹⁸ — only 60 iterations.
The gentleman's set of number theory to master next:
• the extended Euclidean algorithm (the inverse modulo a NON-prime);
• Euler's totient function;
• the Chinese remainder theorem.
Task: compute 2^n mod (10⁹+7) for n = 10¹⁸ (one line with binpow) and the binomial coefficient C(1000, 500) modulo the prime.
Mark the lesson as completed — Level 5 is done!