vi. Harmonic Lemma and Floor Sums

Harmonic lemma: $\lfloor n/i\rfloor$ takes at most $2\sqrt{n}$ distinct values for $1\le i\le n$, and each value occupies one contiguous block $i\in [l,\lfloor n/\lfloor n/l\rfloor \rfloor ]$. So any sum ${\sum }_{i}f(i)g(\lfloor n/i\rfloor )$ with prefix sums of $f$ costs $O(\sqrt{n})$. Floor sums ${\sum }_{i<n}\lfloor (ai+b)/m\rfloor$ follow a Euclid-like recursion in $O(\log )$. Harmonic numbers $H_n=\sum 1/i=\ln n+\gamma +O(1/n)$ explain why “for $i$, loop over multiples of $i$” is $O(n\log n)$.

Block iteration

ll sumFloorDiv(ll n) {                                     // sum_{i=1}^n floor(n / i) = sum_{k<=n} d(k)
    ll s = 0;
    for (ll l = 1, r; l <= n; l = r + 1) { r = n / (n / l); s += (r - l + 1) * (n / l); }
    return s;
}
ll sumMod(ll n, ll k) {                                    // sum_{i=1}^n (k mod i) = n k - sum i floor(k / i)
    i128 s = (i128)n * k;
    for (ll l = 1, r; l <= min(n, k); l = r + 1) { r = min(n, k / (k / l)); s -= (i128)(k / l) * (l + r) * (r - l + 1) / 2; }
    return (ll)s;
}
// all distinct values v = floor(n / i), with an O(1) index (the backbone of Lucy / Min_25 sieves)
struct FloorValues {
    ll n, sq; vector<ll> vals; vector<int> lo, hi;         // lo[v] for v <= sq, hi[n / v] for v > sq
    FloorValues(ll n) : n(n), sq((ll)sqrtl(n)) {
        while (sq * sq > n) sq--; while ((sq + 1) * (sq + 1) <= n) sq++;
        lo.assign(sq + 2, -1); hi.assign(sq + 2, -1);
        for (ll l = 1; l <= n; l = n / (n / l) + 1) { ll v = n / l; (v <= sq ? lo[v] : hi[n / v]) = sz(vals); vals.push_back(v); }
    }
    int id(ll v) const { return v <= sq ? lo[v] : hi[n / v]; }
};

Sum	Block formula
${\sum }_{i\le n}\lfloor n/i\rfloor$ ($={\sum }_{k\le n}d(k)$)	block count times value; hyperbola: $2{\sum }_{i\le \sqrt{n}}\lfloor n/i\rfloor -\lfloor \sqrt{n}{\rfloor }^2$
${\sum }_{i\le n}(k\mathrm{mod}i)$	$nk-\sum i\lfloor k/i\rfloor$, blocks with arithmetic series
${\sum }_d\mu (d)\lfloor n/d\rfloor \lfloor m/d\rfloor$	joint blocks: $r=\min (n/(n/l),m/(m/l))$
${\sum }_d\phi (d)\lfloor n/d{\rfloor }^2$ (gcd sum)	blocks with prefix sums of $\phi$
${\sum }_{i\le n}\lfloor \sqrt{i}\rfloor$	value $v$ on $[v^2,(v+1{)}^2)$: $O(\sqrt{n})$
${\sum }_i\lfloor n/i^2\rfloor$	$i\le \sqrt{n}$ directly

Proof: the harmonic lemma and the block end

For $i\le \sqrt{n}$ there are at most $\sqrt{n}$ values of $i$; for $i>\sqrt{n}$, $\lfloor n/i\rfloor <\sqrt{n}$ takes at most $\sqrt{n}$ values. Since $\lfloor n/i\rfloor$ is non-increasing in $i$, equal values form blocks. For $v=\lfloor n/l\rfloor$: $\lfloor n/i\rfloor \ge v⟺i\le n/v⟺i\le \lfloor n/v\rfloor$, so the block ends at $\lfloor n/v\rfloor$. Joint blocks of two such functions end at the smaller of the two ends; there are $O(\sqrt{n}+\sqrt{m})$ of them. In FloorValues, $\lfloor n/\lfloor n/i\rfloor \rfloor$… each value $v>\sqrt{n}$ equals $\lfloor n/i\rfloor$ for a unique small $i=\lfloor n/v\rfloor \le \sqrt{n}$ (since $\lfloor n/\lfloor n/i\rfloor \rfloor$ maps the block back), so indexing large values by $n/v$ is injective. Also $\lfloor \lfloor n/a\rfloor /b\rfloor =\lfloor n/(ab)\rfloor$, so recursions on these values stay inside the set.

Harmonic numbers

$n$	1	2	5	10	100	1000	$10^6$
$H_n$	1	1.5	2.283	2.929	5.187	7.485	14.393

$\ln (n+1)\le H_n\le 1+\ln n$; $H_n-\ln n\downarrow \gamma \approx 0.5772$. Consequences: ${\sum }_{i\le n}n/i=O(n\log n)$ (divisor lists, sieving over multiples, the “for $i$, for $j$ multiple of $i$” loop, harmonic-step loops like for (j = i; j <= n; j += i)), and ${\sum }_{i\le n}\frac{n}{i}\log \frac{n}{i}$-type bounds stay $O(n{\log }^{2}n)$. Expected values: records / cycles of random permutations ($H_n$), coupon collector ($n{H}_n$).

Proof: the bounds on $H_n$

$1/x$ is decreasing, so ${\int }_i^{i+1}\frac{dx}{x}\le \frac{1}{i}\le {\int }_{i-1}^i\frac{dx}{x}$ for $i\ge 2$. Summing the left inequality over $i=\mathrm{1..}n$ gives $\ln (n+1)\le H_n$; summing the right one over $i=\mathrm{2..}n$ and adding $1$ gives $H_n\le 1+\ln n$. The sequence $H_n-\ln n$ decreases ($\frac{1}{n+1}\le \ln \frac{n+1}{n}$) and is bounded below by $\ln \frac{n+1}{n}>0$, so it converges to a limit $\gamma$.

Floor sums

${\sum }_{i=0}^{n-1}\lfloor (ai+b)/m\rfloor$ counts lattice points under a line; reducing $a,b$ modulo $m$ and swapping the axes gives Euclid’s recursion on $(a,m)$: $O(\log m)$.

ll floorSum(ll n, ll m, ll a, ll b) {                      // sum_{i=0}^{n-1} floor((a i + b) / m), m > 0, any sign a, b
    ll ans = 0;
    if (a < 0) { ll a2 = (a % m + m) % m; ans -= (ll)((i128)n * (n - 1) / 2 * ((a2 - a) / m)); a = a2; }
    if (b < 0) { ll b2 = (b % m + m) % m; ans -= n * ((b2 - b) / m); b = b2; }
    for (;;) {
        if (a >= m) { ans += (ll)((i128)n * (n - 1) / 2 * (a / m)); a %= m; }
        if (b >= m) { ans += n * (b / m); b %= m; }
        i128 yMax = (i128)a * n + b;
        if (yMax < m) break;
        n = (ll)(yMax / m); b = (ll)(yMax % m); swap(m, a);
    }
    return ans;
}

Generalised: with $q_i=\lfloor (ai+b)/c\rfloor$ for $i=\mathrm{0..}n$, the triple $f=\sum q_i$, $g=\sum i{q}_i$, $h=\sum q_i^2$ follows the same recursion (all modulo a prime).

struct FGH { mint f, g, h; };
FGH floorFGH(ll a, ll b, ll c, ll n) {                     // a, b >= 0, c > 0, sums over i = 0..n
    mint N = n, s1 = N * (N + 1) / 2, s2 = N * (N + 1) * (2 * N + 1) / 6;
    if (a >= c || b >= c) {
        FGH t = floorFGH(a % c, b % c, c, n); mint A = a / c, B = b / c;
        return {t.f + A * s1 + B * (N + 1), t.g + A * s2 + B * s1,
                t.h + A * A * s2 + B * B * (N + 1) + A * B * 2 * s1 + B * 2 * t.f + A * 2 * t.g};
    }
    ll m = (ll)(((i128)a * n + b) / c);
    if (m == 0) return {0, 0, 0};
    FGH t = floorFGH(c, c - b - 1, a, m - 1); mint M = m;
    mint f = N * M - t.f;
    mint g = (M * N * (N + 1) - t.h - t.f) / 2;
    mint h = N * M * (M + 1) - t.g * 2 - t.f * 2 - f;
    return {f, g, h};
}

Proof: the floor-sum recursion

Reduction: $\lfloor (ai+b)/m\rfloor =\lfloor a/m\rfloor i+\lfloor b/m\rfloor +\lfloor ((a\mathrm{mod}m)i+(b\mathrm{mod}m))/m\rfloor$, giving the two additive terms (negative $a,b$ are shifted up by multiples of $m$ the same way). Swap: with $0\le a,b<m$, the sum counts lattice points $(i,y)$ with $0\le i<n$ and $1\le y\le (ai+b)/m$. Let $Y=\lfloor (an+b)/m\rfloor$; counting by rows $y$ instead of columns, the points with a given $y$ are the $i$ with $ai\ge my-b$, i.e. $i\ge \lceil (my-b)/a\rceil$, and after substituting $y\to$ the new index the count becomes the same kind of sum with $(n,m,a,b)\to (Y,a,m,(an+b)\mathrm{mod}m)$ as the loop does. Each round replaces $(m,a)$ by $(a,m\mathrm{mod}a)$ after the reduction, so there are $O(\log m)$ rounds, and all intermediate values fit in 128 bits.

FGH: for $a,b<c$, write $q_i={\sum }_{j=0}^{m-1}[j<q_i]$ and $j<q_i⟺c(j+1)\le ai+b⟺i>\lfloor (cj+c-b-1)/a\rfloor =:t_j$. Then $f={\sum }_j(n-t_j)=nm-{\sum }_j{t}_j$, which is the swapped sum. For $g$: ${\sum }_{i}i{q}_i={\sum }_j{\sum }_{i>t_j}i={\sum }_j\frac{n(n+1)-t_j(t_j+1)}{2}$. For $h$: $q_i^2={\sum }_j(2j+1)[j<q_i]$, so $h={\sum }_j(2j+1)(n-t_j)=n{m}^2-2{\sum }_{j}j{t}_j-{\sum }_j{t}_j$. Expressing these with the recursive triple (sums over $j=\mathrm{0..}m-1$ of $t_j$, $j{t}_j$, $t_j^2$) gives the three formulas; the reduction step expands $(Ai+B+q_i^{\prime }{)}^2$ and $i(Ai+B+q_i^{\prime })$ with $\sum i$, $\sum i^2$.