整数同士の切り捨て/切り上げ除算
(Src/Number/IntegerDivision.hpp)

• View this file on GitHub
• Last update: 2023-08-11 15:55:45+09:00
• Include: #include "Src/Number/IntegerDivision.hpp"

概要

整数同士の除算を行い、その結果に床関数や天井関数を適用したものを返す。

ライブラリの使い方

DivFloor

template <class T>
constexpr T DivFloor(T a, T b) 

$\lfloor \frac{a}{b} \rfloor$ を計算する。

制約

• Tは整数型であること
• $b \ne 0$

DivCeil

template <class T>
constexpr T DivCeil(T a, T b)

$\lceil \frac{a}{b} \rceil$ を計算する。

制約

• Tは整数型であること
• $b \ne 0$

Required by

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

Verified with

• AOJ2957 MOD Rush (Test/AOJ/2957.test.cpp)
• ABC132-F Small Products (Test/AtCoder/abc132_f.test.cpp)
• Test/AtCoder/abc191_d.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 <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 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

Back to top page