約数列挙 (Math/enumerate_divisor.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-03-16 00:49:34+09:00
• Include: #include "Math/enumerate_divisor.hpp"

enumerate_divisor

vector<long long> enumerate_divisor(long long n)

入力された値の約数を昇順にしたvectorを返します。

制約

• $0 \lt n$

計算量

• $O(\sqrt n)$

Verified with

• test/Math/enumerate_divisor/aoj-ITP1_3_D.test.cpp
• test/Math/enumerate_divisor/aoj-ITP1_3_D.test2.cpp

Code

#include <bits/stdc++.h>
using namespace std;

vector<long long> enumerate_divisor(long long n)
{
    assert(0 < n);
    vector<long long> dst;
    for (long long i = 1; i * i <= n; i++)
    {
        if (n % i != 0)
            continue;
        dst.push_back(i);
        if (i * i != n)
            dst.push_back(n / i);
    }
    sort(dst.begin(), dst.end());
    return dst;
}

vector<long long> enumerate_divisor(const vector<pair<long long, long long>> &prime_factors)
{
    assert(all_of(prime_factors.begin(), prime_factors.end(), [](const auto &n)
                  { return 0 < n.first && 0 < n.second; }));

    vector<long long> dst;
    auto dfs = [&](int now, long long n, auto dfs) -> void
    {
        if (now == prime_factors.size())
        {
            dst.push_back(n);
            return;
        }

        auto [p, c] = prime_factors[now];
        for (int i = 0; i < c + 1; i++)
        {
            dfs(now + 1, n, dfs);
            if (i != c)
            {
                n *= p;
            }
        }
    };

    dfs(0, 1, dfs);

    sort(dst.begin(), dst.end());

    return dst;
}

#line 1 "Math/enumerate_divisor.hpp"
#include <bits/stdc++.h>
using namespace std;

vector<long long> enumerate_divisor(long long n)
{
    assert(0 < n);
    vector<long long> dst;
    for (long long i = 1; i * i <= n; i++)
    {
        if (n % i != 0)
            continue;
        dst.push_back(i);
        if (i * i != n)
            dst.push_back(n / i);
    }
    sort(dst.begin(), dst.end());
    return dst;
}

vector<long long> enumerate_divisor(const vector<pair<long long, long long>> &prime_factors)
{
    assert(all_of(prime_factors.begin(), prime_factors.end(), [](const auto &n)
                  { return 0 < n.first && 0 < n.second; }));

    vector<long long> dst;
    auto dfs = [&](int now, long long n, auto dfs) -> void
    {
        if (now == prime_factors.size())
        {
            dst.push_back(n);
            return;
        }

        auto [p, c] = prime_factors[now];
        for (int i = 0; i < c + 1; i++)
        {
            dfs(now + 1, n, dfs);
            if (i != c)
            {
                n *= p;
            }
        }
    };

    dfs(0, 1, dfs);

    sort(dst.begin(), dst.end());

    return dst;
}

Back to top page