Internship← Competitive Programming learning pathCompetitive Programming · Module 10 of 10
Number theory and contest strategy
Math tools and habits that win contests.
📖 Key ideas
- GCD by Euclid: gcd(a, b) = gcd(b, a mod b).
- Sieve of Eratosthenes lists primes up to n in O(n log log n).
- Answers are often asked modulo 10^9 + 7; apply mod after every operation.
- Fast power computes a^b mod m in O(log b).
- Strategy: read all problems, solve easy ones first, test edge cases, then upsolve after the contest.
💡 Real-life example: A contest is a marathon: pace yourself, take easy points first and review your run afterwards.
GCDGreatest common divisor
SieveMarks multiples to find primes
Modular arithmeticWork with remainders
UpsolvingSolving missed problems after the contest