math/sqrt_floor.hpp

• View this file on GitHub
• Last update: 2025-02-01 17:57:24+09:00
• Include: #include "math/sqrt_floor.hpp"

Depends on

• math/frac_floor.hpp

Required by

• convolution/convolution_gcd.hpp
• convolution/convolution_lcm.hpp
• convolution/divisor_multiple_transform.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

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/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_quotients.test.cpp
• verify/yosupo_math/prefix_sum_of_multiplicative_function.test.cpp
• verify/yosupo_math/prime_counting.test.cpp

Code

#ifndef KK2_MATH_SQRT_FLOOR_HPP
#define KK2_MATH_SQRT_FLOOR_HPP 1

#include <cmath>

#include "frac_floor.hpp"

namespace kk2 {

template <typename T> T sqrt_floor(T n) {
    assert(n >= 0);
    if (n == T(0)) return 0;
    T x = std::sqrt(n);
    if (x == T(0)) ++x;
    while (x > kk2::fracfloor(n, x)) --x;
    while (x + 1 <= kk2::fracfloor(n, x + 1)) ++x;
    return x;
}

template <typename T> T sqrt_ceil(T n) {
    assert(n >= 0);
    if (n <= T(1)) return n;
    T x = std::sqrt(n);
    if (x == T(0)) ++x;
    while (x < kk2::fracceil(n, x)) ++x;
    while (x - 1 >= kk2::fracceil(n, x - 1)) --x;
    return x;
}

} // namespace kk2

#endif // KK2_MATH_SQRT_FLOOR_HPP

#line 1 "math/sqrt_floor.hpp"



#include <cmath>

#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


#line 7 "math/sqrt_floor.hpp"

namespace kk2 {

template <typename T> T sqrt_floor(T n) {
    assert(n >= 0);
    if (n == T(0)) return 0;
    T x = std::sqrt(n);
    if (x == T(0)) ++x;
    while (x > kk2::fracfloor(n, x)) --x;
    while (x + 1 <= kk2::fracfloor(n, x + 1)) ++x;
    return x;
}

template <typename T> T sqrt_ceil(T n) {
    assert(n >= 0);
    if (n <= T(1)) return n;
    T x = std::sqrt(n);
    if (x == T(0)) ++x;
    while (x < kk2::fracceil(n, x)) ++x;
    while (x - 1 >= kk2::fracceil(n, x - 1)) --x;
    return x;
}

} // namespace kk2

Back to top page