Quotient Blocks
(math/quotient_blocks.hpp)

• View this file on GitHub
• Last update: 2026-10-27 12:15:53+09:00
• Include: #include "math/quotient_blocks.hpp"

概要

• $\lfloor n / i \rfloor$ が等しい $i$ の区間に $[1, n]$ を分ける。

使い方

• quotient_blocks(n): $i \in [l, r)$ で $\lfloor n / i \rfloor = q$ となる {l, r, q} の列を l の昇順で返す。

制約

• $0 \le n$

計算量

• $\mathcal{O}(\sqrt{n})$

Verified with

• test/unit/quotient_blocks.test.cpp

Code

#pragma once
#include <cassert>
#include <vector>
struct quotient_block {
    long long l, r, q;
};
std::vector<quotient_block> quotient_blocks(long long n) {
    assert(n >= 0);
    std::vector<quotient_block> ret;
    for (long long l = 1; l <= n;) {
        long long q = n / l, r = n / q + 1;
        ret.push_back({l, r, q});
        l = r;
    }
    return ret;
}

#line 2 "math/quotient_blocks.hpp"
#include <cassert>
#include <vector>
struct quotient_block {
    long long l, r, q;
};
std::vector<quotient_block> quotient_blocks(long long n) {
    assert(n >= 0);
    std::vector<quotient_block> ret;
    for (long long l = 1; l <= n;) {
        long long q = n / l, r = n / q + 1;
        ret.push_back({l, r, q});
        l = r;
    }
    return ret;
}

Back to top page