test/helloworld/divisor-count-table.test.cpp

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <bits/stdc++.h>

#include "../../Math/Number-Theory/eratosthenes-sieve.hpp"
#include "../../Math/Number-Theory/osa_k.hpp"
#include "../../Math/Number-Theory/divisor-count-table.hpp"

constexpr int N = 1e5;

int divisorCount(int n, const EratosthenesSieve& sieve) {
    int ret = 1;
    for (const auto [value, cnt] : osa_k(n, sieve)) {
        ret *= (cnt + 1);
    }
    return ret;
}

void test_divisorCountTable() {
    const auto dct = divisorCountTable(N);
    const auto sieve = EratosthenesSieve(N);

    for (int i = 1; i <= N; ++i) {
        const auto expected = divisorCount(i, sieve);
        const auto got = dct[i];
        assert(got == expected);
    }

    std::clog << __func__ << " : OK" << std::endl;
}

int main() {
    std::cout << "Hello World" << std::endl;

    test_divisorCountTable();

    return 0;
}

#line 1 "test/helloworld/divisor-count-table.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <bits/stdc++.h>

#line 5 "Math/Number-Theory/eratosthenes-sieve.hpp"

/**
 * @brief Eratosthenes-Sieve (エラトステネスの篩)
 * @see https://qiita.com/rsk0315_h4x/items/ff3b542a4468679fb409
 */
class EratosthenesSieve {
private:
    int m_size;
    std::vector<int> m_minFactor;

public:
    EratosthenesSieve() = default;

    //! [0, n] の範囲で篩を構築する
    explicit EratosthenesSieve(int n_)
        : m_size(n_ + 1)
        , m_minFactor(m_size) {
        std::iota(m_minFactor.begin(), m_minFactor.end(), 0);
        for (int i = 2; i * i < m_size; ++i) {
            if (m_minFactor[i] < i) continue;
            for (int j = i * i; j < m_size; j += i) {
                if (m_minFactor[j] == j) m_minFactor[j] = i;
            }
        }
        m_minFactor[0] = -1;
        if (n_ >= 1) m_minFactor[1] = -1;
    }

    bool isPrime(int x) const {
        assert(0 <= x && x < m_size);
        return m_minFactor[x] == x;
    }

    int minFactor(int x) const {
        assert(0 <= x && x < m_size);
        return m_minFactor[x];
    }
};
#line 2 "Math/Number-Theory/osa_k.hpp"

#line 4 "Math/Number-Theory/osa_k.hpp"

#line 6 "Math/Number-Theory/osa_k.hpp"

/**
 * @brief osa_k() (前計算 $O(N \log \log N)$, 素因数分解 $O(\log N)$)
 * @see https://qiita.com/rsk0315_h4x/items/ff3b542a4468679fb409
 */
std::map<int, int> osa_k(int n, const EratosthenesSieve& es) {
    std::map<int, int> ret;
    while (n > 1) {
        ++ret[es.minFactor(n)];
        n /= es.minFactor(n);
    }
    return ret;
}
#line 2 "Math/Number-Theory/divisor-count-table.hpp"

#line 4 "Math/Number-Theory/divisor-count-table.hpp"

/**
 * @brief divisorCountTable (約数の個数のテーブル, $O(N \log N)$)
 * cnt[i] = i の約数の個数; 範囲は閉区間 [0, N]
 */
std::vector<int> divisorCountTable(int N) {
    std::vector<int> cnt(N + 1);
    for (int d = 1; d <= N; ++d) {
        for (int i = d; i <= N; i += d) ++cnt[i];
    }
    return cnt;
}
#line 7 "test/helloworld/divisor-count-table.test.cpp"

constexpr int N = 1e5;

int divisorCount(int n, const EratosthenesSieve& sieve) {
    int ret = 1;
    for (const auto [value, cnt] : osa_k(n, sieve)) {
        ret *= (cnt + 1);
    }
    return ret;
}

void test_divisorCountTable() {
    const auto dct = divisorCountTable(N);
    const auto sieve = EratosthenesSieve(N);

    for (int i = 1; i <= N; ++i) {
        const auto expected = divisorCount(i, sieve);
        const auto got = dct[i];
        assert(got == expected);
    }

    std::clog << __func__ << " : OK" << std::endl;
}

int main() {
    std::cout << "Hello World" << std::endl;

    test_divisorCountTable();

    return 0;
}