math/frac_floor.hpp

• View this file on GitHub
• Last update: 2025-01-05 04:43:56+09:00
• Include: #include "math/frac_floor.hpp"

Required by

• convolution/convolution_gcd.hpp
• convolution/convolution_lcm.hpp
• convolution/divisor_multiple_transform.hpp
• data_structure/convex_hull_trick_add_monotone.hpp
• math/enumerate_quotients.hpp
• math/multiplicative_function/counting_square_free.hpp
• math/multiplicative_function/prefix_sum.hpp
• math/multiplicative_function/prime_counting.hpp
• math/prime_table.hpp
• math/sqrt_floor.hpp

Verified with

• verify/unit_test/isprime_table_extend.test.cpp
• verify/unit_test/lpf_table_extend.test.cpp
• verify/unit_test/prime_table_extend.test.cpp
• verify/yosupo_convolution/convolution_gcd.test.cpp
• verify/yosupo_convolution/convolution_lcm.test.cpp
• verify/yosupo_math/enumerate_primes.test.cpp
• verify/yosupo_math/enumerate_primes.test.cpp
• verify/yosupo_math/enumerate_quotients.test.cpp
• verify/yosupo_math/prefix_sum_of_multiplicative_function.test.cpp
• verify/yosupo_math/prime_counting.test.cpp

Code

#ifndef KK2_MATH_FRAC_FLOOR_HPP
#define KK2_MATH_FRAC_FLOOR_HPP 1

#include <cassert>

namespace kk2 {

// floor(x) = ceil(x) - 1 (for all x not in Z) ...(1)
// floor(x) = -ceil(-x)   (for all x)          ...(2)

// return floor(a / b)
template <typename T, typename U> constexpr T fracfloor(T a, U b) {
    assert(b != 0);
    if (a % b == 0) return a / b;
    if (a >= 0) return a / b;

    // floor(x) = -ceil(-x)      by (2)
    //          = -floor(-x) - 1 by (1)
    return -((-a) / b) - 1;
}

// return ceil(a / b)
template <typename T, typename U> constexpr T fracceil(T a, U b) {
    assert(b != 0);
    if (a % b == 0) return a / b;
    if (a >= 0) return a / b + 1;

    // ceil(x) = -floor(-x)      by (2)
    return -((-a) / b);
}

} // namespace kk2

#endif // KK2_MATH_FRAC_FLOOR_HPP

#line 1 "math/frac_floor.hpp"



#include <cassert>

namespace kk2 {

// floor(x) = ceil(x) - 1 (for all x not in Z) ...(1)
// floor(x) = -ceil(-x)   (for all x)          ...(2)

// return floor(a / b)
template <typename T, typename U> constexpr T fracfloor(T a, U b) {
    assert(b != 0);
    if (a % b == 0) return a / b;
    if (a >= 0) return a / b;

    // floor(x) = -ceil(-x)      by (2)
    //          = -floor(-x) - 1 by (1)
    return -((-a) / b) - 1;
}

// return ceil(a / b)
template <typename T, typename U> constexpr T fracceil(T a, U b) {
    assert(b != 0);
    if (a % b == 0) return a / b;
    if (a >= 0) return a / b + 1;

    // ceil(x) = -floor(-x)      by (2)
    return -((-a) / b);
}

} // namespace kk2

Back to top page