約数列挙
(Src/Number/Divisor.hpp)

• View this file on GitHub
• Last update: 2024-02-06 11:57:20+09:00
• Include: #include "Src/Number/Divisor.hpp"

概要

$O(\sqrt{v})$ の約数列挙

約数はソートされていない！！！！！

vが0以下だとassertにひっかかる！！！！！

Depends on

• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Verified with

• ABC272-G Yet Another mod M (Test/Manual/abc272_g.test.cpp)

Code

#pragma once

#include "../Template/TypeAlias.hpp"

#include <cassert>
#include <type_traits>
#include <vector>

namespace zawa {

// @remark: 約数はソートされていない
template <class T>
std::vector<T> Divisor(T v) {
    assert(v > static_cast<T>(0));
    std::vector<T> res;
    for (T i{1} ; i * i <= v ; i++) {
        if (v % i) continue;
        res.emplace_back(i);
        if (i * i != v) {
            res.emplace_back(v / i);
        }
    }
    return res;
}

} // namespace zawa

#line 2 "Src/Number/Divisor.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Number/Divisor.hpp"

#include <cassert>
#include <type_traits>
#include <vector>

namespace zawa {

// @remark: 約数はソートされていない
template <class T>
std::vector<T> Divisor(T v) {
    assert(v > static_cast<T>(0));
    std::vector<T> res;
    for (T i{1} ; i * i <= v ; i++) {
        if (v % i) continue;
        res.emplace_back(i);
        if (i * i != v) {
            res.emplace_back(v / i);
        }
    }
    return res;
}

} // namespace zawa

Back to top page