← all categories

Floor Sum Block Trick 9f51b00b

Block/quotient iteration: floor(n/i) takes O(\sqrt n) distinct values as i ranges over [1, n], each held over a contiguous block [i, floor(n / floor(n/i))]. Iterate blocks instead of individual i whenever summing something that depends only on floor(n/i) — this file shows the idiom computing Sum_{i=1}^{n} floor(n/i) mod MOD.

Time: O(\sqrt n). tested

content/math/floor-sum-block-trick.h

ll floorSum(ll n, ll MOD) {
    ll ans = 0;
    for (ll i = 1, hi; i <= n; i = hi + 1) {
        ll q = n / i;
        hi = n / q;
        ll cnt = (hi - i + 1) % MOD;
        ans = (ans + cnt * (q % MOD)) % MOD;
    }
    return ans;
}