Math -> GCD And LCM¶

Euclidean algorithm, Bézout identities, and the way gcd/lcm structure propagates through arrays and constructions.

Microtopics¶

Source	Type
cp-algorithms Euclidean Algorithm	`Reference`
OI Wiki GCD	`Reference`
Principles of Algorithmic Problem Solving	`Reference`

Source	Type
CSES Common Divisors	`Practice`

Source	Type
USACO Guide GCD on Blackboard	`Reference`
USACO Guide Orac and LCM	`Reference`

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Calculate GCD	`AtCoder`	`Easy`	Euclid	Implementation	Euclid's Algorithm	GCD; Euclid	The simplest gcd-only exercise and a good starting point for the track.
Greatest Common Divisor of N Integers	`AtCoder`	`Easy`	Euclid	Implementation	Euclid's Algorithm	GCD; Reduce	Shows how gcd scales from pairs to arrays without adding extra theory.
Least Common Multiple of N Integers	`AtCoder`	`Easy`	Overflow-Safety	Implementation	GCD; Safe Multiplication	LCM; GCD; Overflow	A direct lcm task that reinforces the gcd-based formula and overflow control.
GCD and LCM	`Kattis`	`Easy-Medium`	-	-	-	GCD Formula; LCM Formula; Integer Arithmetic	Straightforward gcd/lcm arithmetic practice.
GCD Pairs	`Kattis`	`Medium`	GCD Counting, Mobius	-	-	Pair Counting; Divisors; Coprime	Uses gcd counting ideas at a pair-of-values level.
GCD on Blackboard	`AtCoder`	`Medium`	Prefix/Suffix GCD	-	-	Remove-One; GCD Array; Prefix Suffix	Classic one-removal gcd optimization.
Orac and LCM	`Codeforces`	`Medium`	Number Theory	Math; Implementation	Prime Factorization; GCD/LCM Identities	GCD; LCM; Prime Exponents	A classic pairwise-lcm/gcd identity problem and a strong conceptual checkpoint.
GCD Harmony	`Kattis`	`Hard`	GCD Constraints, Optimization	-	-	GCD Reasoning; Integer Transform; Number Theory	A deeper gcd-flavored optimization problem.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Common Divisors	`CSES`	`Medium`	Frequency-Ideas, Divisibility	Number Theory	GCD; Divisor Counting	GCD; Divisor Frequency; Maximum GCD; Frequency Over Divisors; Array GCD	Directly about maximizing gcd structure in an array.
LCM on Whiteboard	`AtCoder`	`Medium`	Prime-Factorization	Number Theory; Implementation	LCM Via Maximum Exponents	LCM; Prime Exponents; Set Cover	A richer lcm problem that rewards exponent-level reasoning across many numbers.
Large LCM	`AtCoder`	`Medium`	Overflow-Safety	Implementation; Math	GCD; Overflow-Safe Arithmetic	LCM; Overflow; Large Integers	A standard large-lcm variation where the answer must be capped safely.

Code	Title	Fit	Difficulty	Pattern	Note	Solution
`COMMONDIVISORS`	Common Divisors	`primary`	`medium`	divisor frequency scan; count multiples; maximize pair gcd	Note	Code
`COUNTINGDIVISORS`	Counting Divisors	`secondary`	`easy`	divisor sieve; many queries preprocessing; divisor counting	Note	Code
`CRYPTKEY`	Chìa khóa mã số	`primary`	`hard`	gcd-lcm closure; prime-power characterization; constructibility	Note	Code
`EUCLIDPROBLEM`	Euclid Problem	`primary`	`medium`	-	Note	Code
`GCDONBLACKBOARD`	GCD on Blackboard	`primary`	`medium`	prefix suffix gcd; remove one element; maximize array gcd	Note	Code
`LAMP`	Dàn đèn màu	`secondary`	`hard`	density formula; pairwise coprime products; big integer fractions	Note	Code

python3 scripts/generate_problem_catalog.py