cplib/divisors.hpp

• View this file on GitHub
• Last update: 2025-12-27 20:04:46+09:00
• Include: #include "cplib/divisors.hpp"

Depends on

• cplib/prime_factorization.hpp

Code

#pragma once

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>
#include "cplib/prime_factorization.hpp"

namespace cplib {

// pair(素因数, 指数) の vector を受け取り正の約数を昇順にすべて求める
// 入力の vector が空の場合は {1} を返す
// 計算量は 約数の個数を s として O(slogs)
std::vector<uint64_t> divisors(
    const std::vector<std::pair<uint64_t, uint64_t>>& primes) {
    size_t res_size = 1;
    for (auto [prime, count] : primes) res_size *= count + 1;

    std::vector<uint64_t> result = {1};
    result.reserve(res_size);

    for (auto [prime, count] : primes) {
        size_t tmp_size = result.size();
        for (size_t i = 0; i < tmp_size; ++i) {
            uint64_t prime_power = 1;
            for (uint64_t j = 0; j < count; ++j) {
                prime_power *= prime;
                result.push_back(result[i] * prime_power);
            }
        }
    }
    std::ranges::sort(result);
    return result;
}

// 正の整数 n の正の約数を昇順にすべて求める
// 計算量は O(n^(1/2))
std::vector<uint64_t> divisors(uint64_t n) {
    assert(n > 0);
    std::vector<std::pair<uint64_t, uint64_t>> primes = prime_factorization(n);
    return divisors(primes);
}

}  // namespace cplib

#line 2 "cplib/divisors.hpp"

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>
#line 2 "cplib/prime_factorization.hpp"

#line 7 "cplib/prime_factorization.hpp"

namespace cplib {

// n を素因数分解する
// (素因数, 指数) の pair を要素とする vector を返す
// 計算量は O(n^(1/2))
// n < (2^32-1)^2 でなければならない
std::vector<std::pair<uint64_t, uint64_t>> prime_factorization(uint64_t n) {
    std::vector<std::pair<uint64_t, uint64_t>> result(0);
    // (2^32-1)^2 <= n のとき i^2 がオーバーフローして壊れる
    for (uint64_t i = 2; i * i <= n; ++i) {
        if (n % i != 0) continue;
        uint64_t count = 0;
        while (n % i == 0) {
            ++count;
            n /= i;
        }
        result.emplace_back(i, count);
    }
    if (n > 1) result.emplace_back(n, 1);
    return result;
}

}  // namespace cplib
#line 9 "cplib/divisors.hpp"

namespace cplib {

// pair(素因数, 指数) の vector を受け取り正の約数を昇順にすべて求める
// 入力の vector が空の場合は {1} を返す
// 計算量は 約数の個数を s として O(slogs)
std::vector<uint64_t> divisors(
    const std::vector<std::pair<uint64_t, uint64_t>>& primes) {
    size_t res_size = 1;
    for (auto [prime, count] : primes) res_size *= count + 1;

    std::vector<uint64_t> result = {1};
    result.reserve(res_size);

    for (auto [prime, count] : primes) {
        size_t tmp_size = result.size();
        for (size_t i = 0; i < tmp_size; ++i) {
            uint64_t prime_power = 1;
            for (uint64_t j = 0; j < count; ++j) {
                prime_power *= prime;
                result.push_back(result[i] * prime_power);
            }
        }
    }
    std::ranges::sort(result);
    return result;
}

// 正の整数 n の正の約数を昇順にすべて求める
// 計算量は O(n^(1/2))
std::vector<uint64_t> divisors(uint64_t n) {
    assert(n > 0);
    std::vector<std::pair<uint64_t, uint64_t>> primes = prime_factorization(n);
    return divisors(primes);
}

}  // namespace cplib

Back to top page