商列挙
(Src/Number/EnumerateQuotients.hpp)

• View this file on GitHub
• Last update: 2023-08-12 14:28:20+09:00
• Include: #include "Src/Number/EnumerateQuotients.hpp"

概要

正整数 $n$ に対して、 $n$ の商 $\frac{n}{i} (1\ \le\ i\ \le\ n)$ の切り捨て/切り上げの値、それに対応する $i$ の区間を保持します。

ライブラリの使い方

テンプレート引数

template <class Value>

$n$ の型を指定します。

制約: Valueは符号無し整数型である必要がある

コンストラクタ

(1) constexpr EnumerateQuotients() = default
(2) constexpr EnumerateQuotients(Value n, bool floor = true)

(1) 特に使用することを想定していない。std::vector<EnumerateQuotients>とかやりたくなった時用？

(2) $n$ に対して商を列挙する。floorをtrueにした場合、商の切り捨てが、falseにした場合は商の切り上げが保持される。

• 切り上げの方は競プロの問題でverifyしていない(募: verifyに使える問題)
• デフォルトではtrueが設定されているため、何もしていされなければfloorの方で計算される

計算量: $O(\sqrt{n})$

n

constexpr Value n() const noexcept

$n$ を返す。

計算量: 定数時間

operator[]

constexpr Data operator[](u32 i) const noexcept

$i + 1$ 番目に大きい商の情報にアクセスする。

Dataとは以下のようなクラスです。

class Data {
private:
public:
    constexpr Value quotient() const noexcept // 商を返す
    constexpr Value l() const noexcept // (n / i) = quotient()となる最小のiを返す。
    constexpr Value r() const noexcept // (n / i) < quotient()となる最小のiを返す。
    constexpr std::pair<Value, Value> range() const noexcept // (l, r)をstd::pair型で返す。
    constexpr Value len() const noexcept // (n / i) = quotient()となるiの数を返す。(r() - l())と等価
}

制約: i < size() (size()は後述するメンバで、商の数)

計算量: 定数時間

quotient

constexpr Value quotient(u32 i) const noexcept

$i + 1$ 番目に大きい商にアクセスする。

制約: i < size()

計算量: 定数時間

l

constexpr Value l(u32 i) const noexcept

$i + 1$ 番目に大きい商 $x$ について、 $\frac{n}{i} = x$ となる最小の $i$ を返す。

制約: i < size()

計算量: 定数時間

r

constexpr Value r(u32 i) const noexcept

$i + 1$ 番目に大きい商 $x$ について、 $\frac{n}{i} < x$ となる最小の $i$ を返す。

制約: i < size()

計算量: 定数時間

len

constexpr Value len(u32 i) const noexcept

$i + 1$ 番目に大きい商 $x$ について、 $\frac{n}{i} = x$ となる $i$ の数を返す。

制約: i < size()

計算量: 定数時間

size

constexpr usize size() const noexcept

商の数を返す。

計算量: 定数時間

begin

constexpr typename decltype(seq_)::const_iterator begin() const noexcept

最大の商の情報を持つconst_iteratorを返します。

計算量: 定数時間

end

constexpr typename decltype(seq_)::const_iterator end() const noexcept

最小の商の情報を持つ情報の次のconst_iteratorを返します。

計算量: 定数時間

begin endの役割

EnumerateQuotients eq(n);
for (const auto& e : eq) {

}

とすることで、商の大きい順に商を保持するDataにアクセスすることができます。

アルゴリズム

一般に正整数 $n$ と $i = 1, 2, \dots, n - 1, n$ に対して、 $\lfloor \frac{n}{i}\rfloor$ の種類数は $O(\sqrt{n})$ 個に抑えられます。

なぜなら $\lfloor \frac{n}{i}\rfloor > \sqrt{n}$ を満たす $i$ は $\sqrt{n}$ 以下であり、かつ $\sqrt{n}$ 以上の $i$ について $\lfloor \frac{n}{i}\rfloor\ \le\ \sqrt{n}$ が成り立つからです。

なので、順にそれを取得しているだけです。

Appendix

• https://nyaannyaan.github.io/library/multiplicative-function/prime-counting-faster.hpp
• https://twitter.com/yosupot/status/1624735126163980289

$N\ \le\ 10^{12}$ 程度なら、除算はdouble型で行った方が(十分な精度を持ちながらも)速いという話がある。(zawa::EnumerateQuotientsでは採用していない)

Depends on

• 整数同士の切り捨て/切り上げ除算 (Src/Number/IntegerDivision.hpp)
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Verified with

• AOJ2957 MOD Rush (Test/AOJ/2957.test.cpp)
• ABC132-F Small Products (Test/AtCoder/abc132_f.test.cpp)
• Test/AtCoder/abc230_e.test.cpp
• Test/LC/enumerate_quotients.test.cpp
• Test/My/Number/EnumerateQuotients/ceilBuild.test.cpp

Code

#pragma once

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

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

namespace zawa {

template <class Value>
class EnumerateQuotients {
public:
    class Data {
    private:
        Value quotient_;
        Value l_, r_;
    public:
        Data() = default;
        constexpr Data(Value quotient, Value l, Value r) : quotient_{ quotient }, l_{ l }, r_{ r } {
            assert(l < r);
        }
        
        constexpr Value quotient() const noexcept {
            return quotient_;
        }

        constexpr Value l() const noexcept {
            return l_;
        }

        constexpr Value r() const noexcept {
            return r_;
        }

        constexpr std::pair<Value, Value> range() const noexcept {
            return std::pair{ l_, r_ };
        }

        constexpr Value len() const noexcept {
            return r_ - l_;
        }
    };

private:
    std::vector<Data> seq_;
    Value n_;

    constexpr void templateTypeAssert() const noexcept {
        static_assert(std::is_integral_v<Value>, "Template argument must be unsigned integer type.");
        static_assert(std::is_unsigned_v<Value>, "Template argument must be unsigned integer type.");
    }

    constexpr void floorBuild() noexcept {
        Value l{1U};
        while (l <= n_) {
            Value quotient{ DivFloor(n_, l) };
            Value r{ DivFloor(n_, quotient) + 1 };
            seq_.emplace_back(quotient, l, r);
            l = r;
        } 
    }

    constexpr void ceilBuild() noexcept {
        Value l{1U};
        while (l < n_) {
            Value quotient{ DivCeil(n_, l) };
            Value r{ DivCeil(n_, quotient - 1) };
            seq_.emplace_back(quotient, l, r);
            l = r;
        }
        if (n_) {
            seq_.emplace_back(1U, n_, n_ + 1);
        }
    }

public:
    constexpr EnumerateQuotients() : seq_{}, n_{} {
        templateTypeAssert();
    }

    constexpr EnumerateQuotients(Value n, bool floor = true) : seq_{}, n_{ n } {
        templateTypeAssert();
        floor ? floorBuild() : ceilBuild();
        seq_.shrink_to_fit();
    }

    constexpr Value n() const noexcept {
        return n_;
    }

    constexpr Data operator[](u32 i) const noexcept {
        return seq_[i];
    }

    constexpr Value quotient(u32 i) const noexcept {
        assert(i < seq_.size()); 
        return seq_[i].quotient();
    }

    constexpr Value l(u32 i) const noexcept {
        assert(i < seq_.size()); 
        return seq_[i].l();
    }

    constexpr Value r(u32 i) const noexcept {
        assert(i < seq_.size()); 
        return seq_[i].r();
    }

    constexpr std::pair<Value, Value> range(u32 i) const noexcept {
        assert(i < seq_.size());
        return std::move(seq_[i].range());
    }

    constexpr Value len(u32 i) const noexcept {
        assert(i < seq_.size());
        return seq_[i].len();
    }

    constexpr usize size() const noexcept {
        return seq_.size();
    }

    constexpr typename decltype(seq_)::const_iterator begin() const noexcept {
        return seq_.begin();
    }

    constexpr typename decltype(seq_)::const_iterator end() const noexcept {
        return seq_.end();
    }

};

} // namespace zawa

#line 2 "Src/Number/EnumerateQuotients.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 2 "Src/Number/IntegerDivision.hpp"

#include <type_traits>
#include <cassert>

namespace zawa {

template <class T>
constexpr T DivFloor(T a, T b) {
    static_assert(std::is_integral_v<T>, "DivFloor argument must be Integer");
    assert(b != T{});
    if constexpr (std::is_unsigned_v<T>) {
        return a / b;
    }
    else {
        if (b < 0) {
            a *= -1;
            b *= -1;
        }
        return (a >= 0 ? a / b : (a - b + 1) / b);
    }
}

template <class T>
constexpr T DivCeil(T a, T b) {
    static_assert(std::is_integral_v<T>, "DivCeil argument must be Integer");
    assert(b != T{});
    if constexpr (std::is_unsigned_v<T>) {
        return (a + b - 1) / b;
    }
    else {
        if (b < 0) {
            a *= -1;
            b *= -1;
        }
        return (a >= 0 ? (a + b - 1) / b : a / b);
    }
}

} // namespace zawa
#line 5 "Src/Number/EnumerateQuotients.hpp"

#line 7 "Src/Number/EnumerateQuotients.hpp"
#include <vector>
#include <utility>
#line 10 "Src/Number/EnumerateQuotients.hpp"

namespace zawa {

template <class Value>
class EnumerateQuotients {
public:
    class Data {
    private:
        Value quotient_;
        Value l_, r_;
    public:
        Data() = default;
        constexpr Data(Value quotient, Value l, Value r) : quotient_{ quotient }, l_{ l }, r_{ r } {
            assert(l < r);
        }
        
        constexpr Value quotient() const noexcept {
            return quotient_;
        }

        constexpr Value l() const noexcept {
            return l_;
        }

        constexpr Value r() const noexcept {
            return r_;
        }

        constexpr std::pair<Value, Value> range() const noexcept {
            return std::pair{ l_, r_ };
        }

        constexpr Value len() const noexcept {
            return r_ - l_;
        }
    };

private:
    std::vector<Data> seq_;
    Value n_;

    constexpr void templateTypeAssert() const noexcept {
        static_assert(std::is_integral_v<Value>, "Template argument must be unsigned integer type.");
        static_assert(std::is_unsigned_v<Value>, "Template argument must be unsigned integer type.");
    }

    constexpr void floorBuild() noexcept {
        Value l{1U};
        while (l <= n_) {
            Value quotient{ DivFloor(n_, l) };
            Value r{ DivFloor(n_, quotient) + 1 };
            seq_.emplace_back(quotient, l, r);
            l = r;
        } 
    }

    constexpr void ceilBuild() noexcept {
        Value l{1U};
        while (l < n_) {
            Value quotient{ DivCeil(n_, l) };
            Value r{ DivCeil(n_, quotient - 1) };
            seq_.emplace_back(quotient, l, r);
            l = r;
        }
        if (n_) {
            seq_.emplace_back(1U, n_, n_ + 1);
        }
    }

public:
    constexpr EnumerateQuotients() : seq_{}, n_{} {
        templateTypeAssert();
    }

    constexpr EnumerateQuotients(Value n, bool floor = true) : seq_{}, n_{ n } {
        templateTypeAssert();
        floor ? floorBuild() : ceilBuild();
        seq_.shrink_to_fit();
    }

    constexpr Value n() const noexcept {
        return n_;
    }

    constexpr Data operator[](u32 i) const noexcept {
        return seq_[i];
    }

    constexpr Value quotient(u32 i) const noexcept {
        assert(i < seq_.size()); 
        return seq_[i].quotient();
    }

    constexpr Value l(u32 i) const noexcept {
        assert(i < seq_.size()); 
        return seq_[i].l();
    }

    constexpr Value r(u32 i) const noexcept {
        assert(i < seq_.size()); 
        return seq_[i].r();
    }

    constexpr std::pair<Value, Value> range(u32 i) const noexcept {
        assert(i < seq_.size());
        return std::move(seq_[i].range());
    }

    constexpr Value len(u32 i) const noexcept {
        assert(i < seq_.size());
        return seq_[i].len();
    }

    constexpr usize size() const noexcept {
        return seq_.size();
    }

    constexpr typename decltype(seq_)::const_iterator begin() const noexcept {
        return seq_.begin();
    }

    constexpr typename decltype(seq_)::const_iterator end() const noexcept {
        return seq_.end();
    }

};

} // namespace zawa

Back to top page