test/unit/quotient_blocks.test.cpp

• View this file on GitHub
• Last update: 2026-10-27 12:15:53+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A

Depends on

• Quotient Blocks (math/quotient_blocks.hpp)

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <cassert>
#include <cmath>
#include <iostream>
#include <vector>

#include "math/quotient_blocks.hpp"
void check(long long n) {
    auto bs = quotient_blocks(n);
    long long expect_l = 1;
    for (auto [l, r, q] : bs) {
        assert(l == expect_l && l < r && r <= n + 1);
        assert(n / l == q && n / (r - 1) == q);
        assert(r == n + 1 || n / r < q);
        expect_l = r;
    }
    assert(expect_l == n + 1);
}
int main() {
    for (long long n = 0; n <= 2000; n++) check(n);
    for (long long n : {1000000000000LL, 999999999999LL, 1000003LL * 999983LL, (1LL << 40)}) {
        check(n);
        assert((long long)quotient_blocks(n).size() <= 2 * (long long)std::sqrt((double)n) + 2);
    }
    assert(quotient_blocks(0).empty());
    assert(quotient_blocks(1).size() == 1);
    // Σ_{i=1}^{n} floor(n / i) via blocks equals direct sum
    for (long long n : {1LL, 10LL, 12345LL, 100000LL}) {
        long long direct = 0;
        for (long long i = 1; i <= n; i++) direct += n / i;
        long long blocks = 0;
        for (auto [l, r, q] : quotient_blocks(n)) blocks += (r - l) * q;
        assert(direct == blocks);
    }
    std::cout << "Hello World" << std::endl;
}

#line 1 "test/unit/quotient_blocks.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <cassert>
#include <cmath>
#include <iostream>
#include <vector>

#line 4 "math/quotient_blocks.hpp"
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 8 "test/unit/quotient_blocks.test.cpp"
void check(long long n) {
    auto bs = quotient_blocks(n);
    long long expect_l = 1;
    for (auto [l, r, q] : bs) {
        assert(l == expect_l && l < r && r <= n + 1);
        assert(n / l == q && n / (r - 1) == q);
        assert(r == n + 1 || n / r < q);
        expect_l = r;
    }
    assert(expect_l == n + 1);
}
int main() {
    for (long long n = 0; n <= 2000; n++) check(n);
    for (long long n : {1000000000000LL, 999999999999LL, 1000003LL * 999983LL, (1LL << 40)}) {
        check(n);
        assert((long long)quotient_blocks(n).size() <= 2 * (long long)std::sqrt((double)n) + 2);
    }
    assert(quotient_blocks(0).empty());
    assert(quotient_blocks(1).size() == 1);
    // Σ_{i=1}^{n} floor(n / i) via blocks equals direct sum
    for (long long n : {1LL, 10LL, 12345LL, 100000LL}) {
        long long direct = 0;
        for (long long i = 1; i <= n; i++) direct += n / i;
        long long blocks = 0;
        for (auto [l, r, q] : quotient_blocks(n)) blocks += (r - l) * q;
        assert(direct == blocks);
    }
    std::cout << "Hello World" << std::endl;
}

Back to top page