Math -> Number Theory Basics¶

Divisibility, primes, totients, divisor functions, and the standard multiplicative toolbox of contest number theory.

Microtopics¶

Source	Type
MIT Mathematics for Computer Science	`Reference`
OI Wiki number theory basics	`Reference`
Competitive Programmer's Handbook	`Reference`

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Calculate GCD	`AtCoder`	`Easy`	GCD/LCM	Implementation; Math	Euclid's Algorithm	GCD; Euclid	A minimal Euclidean-algorithm exercise with no extra machinery.
Divisor Enumeration	`AtCoder`	`Easy`	Divisors	Implementation; Math	Divisibility; Sqrt Factorization	Enumeration	A basic divisor-enumeration drill that teaches the square-root loop pattern.
Factorization	`AtCoder`	`Easy`	Primes, Factorization	Implementation; Math	Division	Prime Factorization; Trial Division	The standard first factorization problem before jumping into sieve-heavy tasks.
Greatest Common Divisor of N Integers	`AtCoder`	`Easy`	GCD/LCM	Implementation; Math	Euclid's Algorithm; Iterative Reduction	GCD; Fold/Reduce	A natural follow-up that checks whether you can fold gcd across many values.
Least Common Multiple of N Integers	`AtCoder`	`Easy`	GCD/LCM	Implementation; Math	GCD; Safe Multiplication	LCM; GCD; Overflow Avoidance	A very standard lcm problem that also reinforces overflow-safe formulas.
Primality Test	`AtCoder`	`Easy`	Primes	Implementation; Math	Divisibility; Prime Numbers	Primality; Trial Division	A direct, foundational prime-checking exercise with clear constraints.
Prime Multiples	`CSES`	`Medium`	Inclusion-Exclusion, Primes	-	-	Subset Enumeration; LCM; Counting Multiples	Counts multiples of prime sets with inclusion-exclusion.
Counting Coprime Pairs	`CSES`	`Medium-Hard`	Mobius Inversion, GCD	-	-	Coprime Pairs; Number Theory; Inclusion-Exclusion	A stronger gcd/Mobius counting exercise.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Counting Divisors	`CSES`	`Easy`	Divisors, Factorization, Prime Factorization, Divisor Counting	Math; Implementation	Exponent Counting	Divisor-Count; Sieve; Tau(n)	Direct divisor-counting from prime exponents.
Next Prime	`CSES`	`Easy-Medium`	Primes, Sieving, Primality Testing	Implementation; Number Theory	Search Over Integers	Prime Search; Miller-Rabin-Style Thinking; Next Prime; Miller-Rabin; Trial Division	Good basic prime-search / primality practice.
Common Divisors	`CSES`	`Medium`	GCD/LCM, Frequency-Ideas	Number Theory; Sieving	GCD; Divisor Counting	GCD; Max-Frequency Divisor	A classic gcd-frequency problem that pushes beyond one-off Euclid calls.
Sum of Divisors	`CSES`	`Medium`	Divisors, Prefix-Sums, Divisor Sums, Arithmetical Functions	Math; Optimization	Floor-Division Grouping	Sigma Function; Divisor Summatory Function; Sigma(n); Floor Division; Mod Arithmetic	Core multiplicative-function summation.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Divisor Analysis	`CSES`	`Medium`	Divisors, Modular-Arithmetic, Prime Factorization, Multiplicative Functions	Math; Precomputation	Geometric Series	Number Of Divisors; Sum Of Divisors; Product Of Divisors	Bundle of the three textbook divisor-function formulas.

Code	Title	Fit	Difficulty	Pattern	Note	Solution
`COMMONDIVISORS`	Common Divisors	`secondary`	`medium`	divisor frequency scan; count multiples; maximize pair gcd	Note	Code
`COUNTINGDIVISORS`	Counting Divisors	`primary`	`easy`	divisor sieve; many queries preprocessing; divisor counting	Note	Code
`CRYPTKEY`	Chìa khóa mã số	`secondary`	`hard`	gcd-lcm closure; prime-power characterization; constructibility	Note	Code
`GCDONBLACKBOARD`	GCD on Blackboard	`secondary`	`medium`	prefix suffix gcd; remove one element; maximize array gcd	Note	Code
`LAMP`	Dàn đèn màu	`primary`	`hard`	density formula; pairwise coprime products; big integer fractions	Note	Code
`PRIMEMULTIPLES`	Prime Multiples	`secondary`	`medium`	subset inclusion exclusion; overflow safe lcm product; count divisible numbers	Note	Code
`VMSCALE`	Chiếc cân kỳ diệu	`secondary`	`hard`	budget dp; balanced ternary; decision-tree optimization	Note	Code

python3 scripts/generate_problem_catalog.py