kpr/math/divisors.hpp

View this file on GitHub
Last update: 2023-05-30 09:27:18+09:00
Include: #include "kpr/math/divisors.hpp"

Depends on

kpr/meta/setting.hpp

Required by

Code

#pragma once
#include <cstdint>
#include <vector>
#include "../meta/setting.hpp"

namespace kpr {
    // 全ての正の約数を返す

    [[maybe_unused]] inline constexpr struct {
        std::vector<KYOPRO_BASE_INT> operator ()(std::uint_fast64_t n) const {
            std::vector<KYOPRO_BASE_INT> lower, upper;
            std::uint_fast64_t i;
            for (i = 1; i * i < n; ++i) if (n % i == 0) {
                lower.emplace_back(i);
                upper.emplace_back(n / i);
            }
            if (i * i == n) lower.emplace_back(i);
            lower.insert(end(lower), upper.rbegin(), upper.rend());
            return lower;
        }
    } divisors;
} // namespace kpr

#line 2 "kpr/math/divisors.hpp"
#include <cstdint>
#include <vector>
#line 3 "kpr/meta/setting.hpp"

#ifndef KYOPRO_BASE_INT
// 基本符号付き整数型

#define KYOPRO_BASE_INT std::int64_t
#endif

#ifndef KYOPRO_BASE_UINT
// 基本符号なし整数型

#define KYOPRO_BASE_UINT std::uint64_t
#endif

#ifndef KYOPRO_BASE_FLOAT
// 基本浮動小数点数型

#define KYOPRO_BASE_FLOAT double
#endif

#ifndef KYOPRO_LL
// ll

#define KYOPRO_LL long long
#endif

#ifndef KYOPRO_LF
// lf

#define KYOPRO_LF double
#endif

#ifndef KYOPRO_MINT
// mint

#define KYOPRO_MINT kpr::ModInt<mod>
#endif

#ifndef KYOPRO_DEFAULT_MOD
// 問題で設定されたmod

#define KYOPRO_DEFAULT_MOD (static_cast<KYOPRO_BASE_UINT>(998244353))
#endif

#ifndef KYOPRO_DECIMAL_PRECISION
// 小数精度(桁)

#define KYOPRO_DECIMAL_PRECISION (static_cast<KYOPRO_BASE_UINT>(12))
#endif

#ifndef KYOPRO_INF_DIV
// 無限大を表す整数が最大値の何分の一かを表す

#define KYOPRO_INF_DIV (static_cast<KYOPRO_BASE_UINT>(3))
#endif

#ifndef KYOPRO_BUFFER_SIZE
// デフォルトのバッファサイズ

#define KYOPRO_BUFFER_SIZE (static_cast<KYOPRO_BASE_UINT>(2048))
#endif

#ifndef KYOPRO_BINOM_MOD_MAX
// デフォルトのBinomModの計算上限

#define KYOPRO_BINOM_MOD_MAX (static_cast<KYOPRO_BASE_UINT>(1000000))
#endif
#line 5 "kpr/math/divisors.hpp"

namespace kpr {
    // 全ての正の約数を返す

    [[maybe_unused]] inline constexpr struct {
        std::vector<KYOPRO_BASE_INT> operator ()(std::uint_fast64_t n) const {
            std::vector<KYOPRO_BASE_INT> lower, upper;
            std::uint_fast64_t i;
            for (i = 1; i * i < n; ++i) if (n % i == 0) {
                lower.emplace_back(i);
                upper.emplace_back(n / i);
            }
            if (i * i == n) lower.emplace_back(i);
            lower.insert(end(lower), upper.rbegin(), upper.rend());
            return lower;
        }
    } divisors;
} // namespace kpr