Prefix Sums Of Number-Theoretic Functions¶

Summatory arithmetic functions opened through one direct Dirichlet convolution, then compressed with quotient grouping on equal floor-division blocks.

Topic slug: math/dirichlet-prefix-sums
Tutorial page: Open tutorial
Ladder page: Open ladder
Repo problems currently tagged here: 1
Repo companion pages: 4
Curated external problems: 2

Microtopics¶

dirichlet-convolution
summatory-sigma
sigma-equals-one-convolution-id
floor-division-blocks
quotient-grouping
harmonic-lemma

Learning Sources¶

Source	Type
USACO Guide Prefix Sums of Number-Theoretic Functions (Part 1)	`Reference`
cp-algorithms Number of divisors / sum of divisors	`Reference`

Practice Sources¶

Source	Type
CSES Sum of Divisors	`Practice`

Repo Companion Material¶

Material	Type
Dirichlet prefix sums hot sheet	`quick reference`
Sum of Divisors	`flagship note`
Template Library exact starter route	`starter route`
Mobius And Multiplicative Counting	`compare point`

Curated External Problems¶

Core¶

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Sum of Divisors	`CSES`	`Medium`	Summatory Arithmetic Functions	Math; Implementation	Number Theory Basics; Arithmetic Progression Sums; Floor Division Grouping	Dirichlet Convolution; Sigma Function; Quotient Grouping; Harmonic Lemma	The cleanest first benchmark where sigma = 1 * id opens a divisor-side sum and equal floor(n / d) quotients collapse the runtime to O(sqrt(n)).

Stretch¶

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Totient sums	`CSES`	`Hard`	Summatory Arithmetic Functions	Math; Implementation	Dirichlet Convolution; Quotient Grouping; Euler Totient	Totient; Prefix Sums; Quotient Grouping; Follow-Up	A useful compare point once the first direct sigma-prefix route is trusted; the same quotient-grouping worldview survives, but the arithmetic function is no longer available by one immediate convolution expansion.

Repo Problems¶

Code	Title	Fit	Difficulty	Pattern	Note	Solution
`SUMOFDIVISORS`	Sum of Divisors	`primary`	`medium`	-	Note	Code

Regeneration¶

python3 scripts/generate_problem_catalog.py