Stage 2 of 10 · 7 lessons · ~3 weeks

Maths basics

Learn the number theory contests use from the easiest rounds upwards: modular arithmetic, gcd, primes and divisors, fast powers and invariants, then inverses and counting under a modulus.

Start: Modular arithmetic

Lessons· one lesson for each topic, in this order

Do this

Write modular add, subtract and multiply helpers and test them with negative results.
Write fast exponentiation from memory and check it against a slow loop.
Write a sieve up to 10^7 and time it.
Solve 5 CSES Mathematics problems.
Solve 5 Codeforces problems tagged number theory near your rating.
For one parity or invariant problem, write down the invariant before coding.

Start with

BookFree
Competitive Programmer's Handbook
Antti Laaksonen · Beginner
Section 1.5 covers the maths basics and Chapter 21 covers number theory, from primes to modular inverses

Practise

CSES Problem Set
The Mathematics section: exponentiation, counting divisors and binomial coefficients
Codeforces
Filter the problem set by the number theory and math tags, near your rating

Keep handy

Algorithms for Competitive Programming (cp-algorithms)
The Algebra section explains the sieve, fast power, Euclid and modular inverses with proofs

Also worth your time

Binary Exponentiation (opens in a new tab)Read
The idea, the code and a list of problems where fast power is the key step
Introduction to AlgorithmsGo deeperPaid
The number-theoretic algorithms chapter goes deeper into Euclid, modular arithmetic and primality

Before moving on: Fast power, sieve and trial division written from memory, and 10 maths problems solved across CSES Mathematics and Codeforces problems tagged number theory at your level.

Tauseef's advice

Contest maths is a small toolkit used often, not a degree. Modular arithmetic, gcd, primes and fast power come up constantly, so make them automatic. When a problem looks like maths, try small cases by hand first: the pattern is usually visible by n = 6.