Math -> Mobius And Multiplicative Counting¶

Divisor-structured inclusion-exclusion, Mobius cancellation, and multiplicative counting over multiples using one linear sieve plus one divisor-frequency sweep.

Topic slug: math/mobius-multiplicative
Tutorial page: Open tutorial
Ladder page: Open ladder
Repo problems currently tagged here: 1
Repo companion pages: 3
Curated external problems: 1

Microtopics¶

mobius-function
mobius-inversion
divisor-frequency
coprime-pair-counting
linear-sieve
multiplicative-counting

Learning Sources¶

Source	Type
OI Wiki Mobius inversion formula	`Reference`
cp-algorithms Linear Sieve	`Reference`
cp-algorithms Inclusion-Exclusion Principle	`Reference`
Competitive Programmer's Handbook	`Reference`

Practice Sources¶

Source	Type
CSES Counting Coprime Pairs	`Practice`

Repo Companion Material¶

Material	Type
Mobius hot sheet	`quick reference`
Counting Coprime Pairs	`flagship note`
Template Library exact starter route	`starter route`

Curated External Problems¶

Core¶

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Counting Coprime Pairs	`CSES`	`Medium`	Coprime Pair Counting	Math; Implementation	Number Theory Basics; Inclusion-Exclusion; Linear Sieve	Mobius Function; Divisor Frequency; Coprime Pairs; Linear Sieve	The cleanest first benchmark where divisor frequencies plus Mobius cancellation replace pairwise gcd checks entirely.

Repo Problems¶

Code	Title	Fit	Difficulty	Pattern	Note	Solution
`COUNTINGCOPRIMEPAIRS`	Counting Coprime Pairs	`primary`	`medium`	-	Note	Code

Regeneration¶

python3 scripts/generate_problem_catalog.py