∑MathIntermediate

Harmonic Lemma

Key Points

•
The Harmonic Lemma says that the values of $⌊$ n/i $⌋$ only change about 2 $n$ times, so you can iterate those value blocks in O( $n$ ) instead of O(n).
•
A classic identity is $\sum_{i = 1}^{n}$ d(i) = $\sum_{i = 1}^{n}$ $⌊$ n/i $⌋$ , letting you compute the summatory divisor count in O( $n$ ).
•
Block decomposition uses r = $⌊$ n / $⌊$ n/l $⌋$ $⌋$ to jump to the end of a constant-value segment in O(1).
•
The sum $\sum_{i = 1}^{n}$ $⌊$ n/i $⌋$ is O(n $lo g$ n) because it behaves like n times the harmonic series.
•
This trick powers many number-theory and DP optimizations whenever indices appear as n/k or $⌊$ n/i $⌋$ .
•
You can combine block decomposition with prefix sums to compute expressions like $\sum$ a[i] $⌊$ n/i $⌋$ in O( $n$ ).
•
In problems with floor-division structure, block iteration often turns an O(n) loop into O( $n$ ) while keeping memory O(1) or O(n) for prefix sums.
•
The method is sometimes called the hyperbola method or integer-division trick in competitive programming.

Prerequisites

→Floor and ceiling functions — Understanding how ⌊x⌋ behaves and how to invert inequalities is the basis of deriving block endpoints.
→Harmonic series and logarithms — The O(n log n) bound uses that H_n grows like log n.
→Prefix sums — Needed to aggregate weighted ranges [l, r] in O(1).
→Basic number theory (divisors) — Identities like ∑ d(i) = ∑ ⌊n/k⌋ arise from counting divisor pairs.
→Integer overflow awareness — Block computations involve products like v·len that may exceed 32-bit limits.

Detailed Explanation

Tap terms for definitions

01Overview

Imagine looping i = 1..n and reading the integer part of n divided by i, i.e., floor(n/i). At first glance, this seems to need O(n) steps. The Harmonic Lemma reveals a hidden structure: floor(n/i) does not change at every i; it stays constant over long stretches (blocks) and only changes about 2√n times. This lets us jump over entire blocks at once. The consequence is powerful: many sums involving floor(n/i) can be evaluated in O(√n) instead of O(n). Hook: Instead of reading every page of a 1000-page book, suppose you could read only the pages where the topic changes—maybe just 60–70 pages. The Harmonic Lemma is like flipping to those change points for floor divisions. Concept: The key observation is that if floor(n/i) = v, then all i in some contiguous interval [l, r] share the same value v. With simple algebra, we can compute r from l (or l from v) in O(1). That means a for loop can jump directly from one block to the next, processing each block in constant time. Example: To compute S = ∑_{i=1}^{n} floor(n/i), we iterate over blocks [l, r] where floor(n/i) is constant v. We add v·(r−l+1) to S and jump l to r+1. This yields an O(√n) algorithm with tiny memory.

02Intuition & Analogies

Think of pouring candies (n candies) into bags of sizes i = 1, 2, 3, …; the number of full bags you can fill is floor(n/i). For small i, the bag is small, so you fill many bags (large value). For large i, the bag is large, so you fill few bags (small value). As i increases, floor(n/i) decreases, but not one-by-one every step. It often stays the same across several consecutive i’s—those are blocks. For example, with n = 100, floor(100/1)=100, floor(100/2)=50, floor(100/3)=33, …; near i = 50..100, many consecutive i give 1 or 2. If you only care about how many full bags you get (the value), you can jump to the next i where that number changes, skipping everything in between. A useful mental picture: Write all divisors of numbers up to n as grid points (i, j) with i·j ≤ n. Counting by rows (fix i) is like summing floor(n/i); counting by columns (fix floor(n/i)) groups many points together. The border i·j = n is a hyperbola, which is why this trick is sometimes called the hyperbola method. Below the hyperbola, points cluster heavily near the axes, meaning many i share the same floor value—perfect for block jumps. In daily life, if bus arrivals are grouped in time windows, you don’t check every minute; you check when the schedule changes. Likewise, we step through i only where floor(n/i) changes, which happens about 2√n times.

03Formal Definition

For a fixed integer

n \geq 1

, define the function f(i) =

⌊

n/i

⌋

for integers

i \geq 1

. The set of distinct values taken by f is V = {

⌊

n/i

⌋

: 1 ≤

i \leq n}

. For any v ∈ V, the indices i with f(i) = v form a contiguous interval [l, r] with l =

\left\lfloor

\frac{n}{v + 1}

\right\rfloor

+ 1 and r =

\left\lfloor

\frac{n}{v}

\right\rfloor

. Moreover, the number of distinct values satisfies

∣ V ∣

= O(

n

). Equivalently, the values of f change at most about 2

⌊

n

⌋

times. The Harmonic Lemma (integer-division block property) asserts that we can enumerate all maximal intervals [l, r] on which f is constant by iterating l and jumping to r via r =

\left\lfloor

\frac{n}{⌊ n / l ⌋}

\right\rfloor

. This yields an O(

n

) loop count. A common corollary is the bound

\sum_{i = 1}^{n}

⌊

n/i

⌋

= O(n

lo g

n), derived from

⌊

n/i

⌋

≤ n/i and the harmonic series bound

\sum_{i = 1}^{n}

1/i = O(

lo g

n).

04When to Use

Use this technique when your summation or DP transitions repeatedly use terms of the form \lfloor n/i \rfloor or n/i as an index/value. Common cases:

Summatory divisor problems: Compute \sum_{i=1}^{n} d(i) using the identity \sum_{i=1}^{n} d(i) = \sum_{k=1}^{n} \lfloor n/k \rfloor.
Hyperbola-method rearrangements: Split lattice point counts under i·j ≤ n into two short sums around \sqrt{n}.
Weighted sums: Evaluate \sum_{i=1}^{n} a(i),\lfloor n/i \rfloor using block decomposition plus a prefix sum of a(i).
DP with floor transitions: If transitions depend only on v = \lfloor n/i \rfloor, you can process ranges with the same v together.
Sieve-like computations: In multiplicative-function summatory problems that involve \lfloor n/i \rfloor (e.g., using Möbius or Euler’s totient in convolution identities), block iteration reduces runtime from O(n) to O(\sqrt{n}) when combined with precomputed prefix sums or small sieves. Aim for this method when constraints make O(n) too slow (n up to 1e12 in math-y problems, or n up to 1e7–1e8 with tight time limits) and the structure involves integer division by i.

⚠️Common Mistakes

Off-by-one in block boundaries: The interval is [l, r] with r = \lfloor n / \lfloor n/l \rfloor \rfloor. Forgetting the floor around n/l or using r = \lfloor n/(\lfloor n/l\rfloor+1) \rfloor is incorrect.
Using 32-bit integers: For n up to 1e12 or more, use 64-bit integers (long long in C++). Multiplications like v*(r-l+1) can overflow 32-bit types.
Forgetting that weights vary: Block decomposition assumes the floor value is constant, but if your term includes i itself (e.g., a(i) depends on i), you need a prefix sum to aggregate over [l, r] in O(1); otherwise you revert to O(n).
Double counting near \sqrt{n} in hyperbola splits: When using 2∑_{i≤√n} ⌊n/i⌋ − ⌊√n⌋^2, check whether the diagonal i = j is counted once.
Assuming O(\sqrt{n}) memory is always enough: Some applications (Möbius/φ summatory) also need sieve arrays or memoization; memory may grow to O(n) if you’re not careful.
Missing termination: Always advance l to r+1. If you advance by +1, you lose the speedup and risk infinite loops when values repeat.

Key Formulas

Harmonic bound

i = 1 \sum n ⌊ \frac{n}{i} ⌋ \leq n i = 1 \sum n \frac{1}{i} = n H_{n} = O (n lo g n)

Explanation: Since $⌊$ n/i $⌋$ ≤ n/i, the sum is at most n times the harmonic number $H_{n}$ . Because $H_{n}$ grows like log n, the overall sum is O(n log n).

Block interval

{i : ⌊ \frac{n}{i} ⌋ = v} = [⌊ \frac{n}{v + 1} ⌋ + 1, ⌊ \frac{n}{v} ⌋]

Explanation: All indices i that give the same floor value v form one contiguous block. The left and right endpoints are computed from n and v.

Jump-to-right endpoint

r = ⌊ \frac{n}{⌊ n / l ⌋} ⌋

Explanation: Given the current left endpoint l, the floor value v = $⌊$ n/l $⌋$ stays constant until r. This formula computes that r directly in O(1).

Divisor-sum identity

i = 1 \sum n d (i) = k = 1 \sum n ⌊ \frac{n}{k} ⌋

Explanation: Each pair (d, m) with d· $m \leq n$ corresponds to a divisor of some number up to n. Counting by d or by the quotient gives this identity, enabling O(√n) computation.

Hyperbola split

i = 1 \sum n ⌊ \frac{n}{i} ⌋ = 2 i = 1 \sum ⌊ n ⌋ ⌊ \frac{n}{i} ⌋ - ⌊ n ⌋^{2}

Explanation: The lattice points under $ij \leq n$ are symmetric across $i = j$ . Doubling the count up to √n and subtracting the diagonal avoids double counting.

Harmonic asymptotic

H_{n} = i = 1 \sum n \frac{1}{i} = ln n + γ + O (\frac{1}{n})

Explanation: The harmonic number grows like the natural logarithm plus Euler–Mascheroni constant $γ .$ It explains the n log n behavior of related sums.

Distinct values count

∣ {⌊ n / i ⌋ : 1 \leq i \leq n} ∣ = O (n)

Explanation: Values above √n occur only O(√n) times; values below √n are at most √n distinct. Together this bounds the number of blocks.

Complexity Analysis

The harmonic block iteration traverses only the distinct values of v = ⌊n/i⌋. For i ≤ ⌊√n⌋, each i yields a distinct v ≥ √n, so there are at most √n such values. For i > √n, the values satisfy v < √n, so there are at most √n more. Hence the number of blocks is O(√n). The standard loop for (

l = 1;

l <= n;

l = r + 1

) {

v = n / l;

r = n / v;

... } advances l by jumping to the right endpoint r of the current block in O(1) time, making the total runtime O(√n) independent of n’s magnitude within each block. Space complexity is typically O(1) if we only accumulate counts like ∑⌊n/i⌋. When weights depend on i (e.g., ∑ a[i] ⌊n/i⌋), we precompute a prefix sum array P in O(n) time and O(n) space; then each block contributes P[r]−P[l−1], still keeping the main loop O(√n). Therefore, the overall complexity becomes O(n + √n) time and O(n) space with prefix sums. If we also include a sieve for arithmetic functions (

μ,

φ),

the sieve adds O(N) time and O(N) space for N up to your precomputation bound; the harmonic loop remains O(√n). In contrast, a naive summation over

i = 1

..n is O(n). For n as large as 10^12, O(n) is infeasible, while O(√n) ≈ 10^6 is manageable. Even for n ≈ 10^7, the block method reduces constant factors significantly because it executes about 2√n iterations instead of n, and each iteration performs O(1) arithmetic and at most two prefix-sum accesses.

Code Examples

Compute S(n) = \sum_{i=1}^{n} \lfloor n/i \rfloor in O(\sqrt{n})

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Computes S(n) = sum_{i=1}^{n} floor(n / i) using harmonic block iteration.
5 // Time: O(sqrt(n)), Space: O(1)
6 
7 int main() {
8     ios::sync_with_stdio(false);
9     cin.tie(nullptr);
10 
11     long long n;
12     if (!(cin >> n)) return 0;
13 
14     long long ans = 0;
15     for (long long l = 1; l <= n; ) {
16         long long v = n / l;                 // current constant value of floor(n / i)
17         long long r = n / v;                 // last index with the same value
18         // All i in [l, r] have floor(n / i) == v
19         ans += v * (r - l + 1);              // add v for each i in the block
20         l = r + 1;                           // jump to the next block
21     }
22 
23     cout << ans << '\n';
24     return 0;
25 }
26

We iterate only over blocks of indices where floor(n/i) is constant. For each block [l, r], the value v = n/l persists, and r = n/v is computed in O(1). Each block contributes v times its length to the sum. The loop runs about 2\sqrt{n} iterations.

Time: O(\sqrt{n})Space: O(1)

Summatory divisor count D(n) = \sum_{i=1}^{n} d(i) via \sum_{k=1}^{n} \lfloor n/k \rfloor

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Computes D(n) = sum_{i=1}^{n} d(i) using the identity
5 // D(n) = sum_{k=1}^{n} floor(n / k) and harmonic blocks.
6 // Time: O(sqrt(n)), Space: O(1)
7 
8 int main() {
9     ios::sync_with_stdio(false);
10     cin.tie(nullptr);
11 
12     long long n;
13     if (!(cin >> n)) return 0;
14 
15     long long D = 0;
16     for (long long l = 1; l <= n; ) {
17         long long v = n / l;     // quotient value
18         long long r = n / v;     // last k with floor(n/k) == v
19         // There are (r - l + 1) terms each equal to v
20         D += v * (r - l + 1);
21         l = r + 1;
22     }
23 
24     cout << D << '\n';
25     return 0;
26 }
27

Each integer m ≤ n contributes 1 to d(i) for every divisor i of m. Counting pairs (i, m/i) with i·(m/i) ≤ n via the quotient k = \lfloor n/i \rfloor yields the identity D(n) = ∑_{k=1}^{n} \lfloor n/k \rfloor. We then compute this sum in O(\sqrt{n}) using block jumps.

Time: O(\sqrt{n})Space: O(1)

Weighted sum: Compute \sum_{i=1}^{n} a[i] \cdot \lfloor n/i \rfloor using prefix sums + blocks

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Given an array a[1..n], compute S = sum_{i=1}^{n} a[i] * floor(n / i)
5 // using harmonic blocks and a prefix-sum array.
6 // Time: O(n + sqrt(n)), Space: O(n)
7 
8 int main() {
9     ios::sync_with_stdio(false);
10     cin.tie(nullptr);
11 
12     int n;
13     if (!(cin >> n)) return 0;
14     vector<long long> a(n + 1), pref(n + 1);
15     for (int i = 1; i <= n; ++i) cin >> a[i];
16 
17     // Build prefix sums: pref[i] = a[1] + ... + a[i]
18     for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + a[i];
19 
20     auto range_sum = [&](int l, int r) -> long long {
21         if (l > r) return 0LL;
22         return pref[r] - pref[l - 1];
23     };
24 
25     long long ans = 0;
26     for (long long l = 1; l <= n; ) {
27         long long v = n / l;           // constant multiplier for this block
28         long long r = n / v;           // last index with same floor value
29         if (r > n) r = n;              // guard, though n/v <= n always
30         // Sum a[l..r] in O(1) via prefix sums, then multiply by v
31         ans += v * range_sum((int)l, (int)r);
32         l = r + 1;
33     }
34 
35     cout << ans << '\n';
36     return 0;
37 }
38

If a weight depends on i, we combine block decomposition with a prefix-sum array. Each block [l, r] contributes v times the sum of a[i] over that block, which we obtain in O(1) using prefix sums. The number of blocks is O(\sqrt{n}), so the main loop is fast.

Time: O(n + \sqrt{n})Space: O(n)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Computes S(n) = sum_{i=1}^{n} floor(n / i) using harmonic block iteration.
5	// Time: O(sqrt(n)), Space: O(1)
6
7	int main() {
8	ios::sync_with_stdio(false);
9	cin.tie(nullptr);
10
11	long long n;
12	if (!(cin >> n)) return 0;
13
14	long long ans = 0;
15	for (long long l = 1; l <= n; ) {
16	long long v = n / l; // current constant value of floor(n / i)
17	long long r = n / v; // last index with the same value
18	// All i in [l, r] have floor(n / i) == v
19	ans += v * (r - l + 1); // add v for each i in the block
20	l = r + 1; // jump to the next block
21	}
22
23	cout << ans << '\n';
24	return 0;
25	}
26

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Computes D(n) = sum_{i=1}^{n} d(i) using the identity
5	// D(n) = sum_{k=1}^{n} floor(n / k) and harmonic blocks.
6	// Time: O(sqrt(n)), Space: O(1)
7
8	int main() {
9	ios::sync_with_stdio(false);
10	cin.tie(nullptr);
11
12	long long n;
13	if (!(cin >> n)) return 0;
14
15	long long D = 0;
16	for (long long l = 1; l <= n; ) {
17	long long v = n / l; // quotient value
18	long long r = n / v; // last k with floor(n/k) == v
19	// There are (r - l + 1) terms each equal to v
20	D += v * (r - l + 1);
21	l = r + 1;
22	}
23
24	cout << D << '\n';
25	return 0;
26	}
27

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Given an array a[1..n], compute S = sum_{i=1}^{n} a[i] * floor(n / i)
5	// using harmonic blocks and a prefix-sum array.
6	// Time: O(n + sqrt(n)), Space: O(n)
7
8	int main() {
9	ios::sync_with_stdio(false);
10	cin.tie(nullptr);
11
12	int n;
13	if (!(cin >> n)) return 0;
14	vector<long long> a(n + 1), pref(n + 1);
15	for (int i = 1; i <= n; ++i) cin >> a[i];
16
17	// Build prefix sums: pref[i] = a[1] + ... + a[i]
18	for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + a[i];
19
20	auto range_sum = [&](int l, int r) -> long long {
21	if (l > r) return 0LL;
22	return pref[r] - pref[l - 1];
23	};
24
25	long long ans = 0;
26	for (long long l = 1; l <= n; ) {
27	long long v = n / l; // constant multiplier for this block
28	long long r = n / v; // last index with same floor value
29	if (r > n) r = n; // guard, though n/v <= n always
30	// Sum a[l..r] in O(1) via prefix sums, then multiply by v
31	ans += v * range_sum((int)l, (int)r);
32	l = r + 1;
33	}
34
35	cout << ans << '\n';
36	return 0;
37	}
38