This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A" #include <cassert> #include <iostream> #include "library/number/find_denominators.hpp" using suisen::fld_denominators_positive; using suisen::fld_denominators_negative; using suisen::cld_denominators_positive; using suisen::cld_denominators_negative; template <typename T> constexpr inline int pow_m1(T n) { return -(n & 1) | 1; } template <> constexpr inline int pow_m1<bool>(bool n) { return -int(n) | 1; } template <typename T> constexpr inline T fld(const T x, const T y) { return (x ^ y) >= 0 ? x / y : (x - (y + pow_m1(y >= 0))) / y; } template <typename T> constexpr inline T cld(const T x, const T y) { return (x ^ y) <= 0 ? x / y : (x + (y + pow_m1(y >= 0))) / y; } bool in(const std::optional<std::pair<int, int>> &r, int x) { return r.has_value() and r->first <= x and x <= r->second; } bool out(const std::optional<std::pair<int, int>> &r, int x) { return not r.has_value() or x < r->first or x > r->second; } void cld_test(int n, int q) { auto res_pos = cld_denominators_positive(n, q, 100); if (res_pos.has_value()) { auto [l, r] = *res_pos; assert(1 <= l and r <= 100); } for (int x = 1; x <= 100; ++x) { if (not (cld(n, x) == q ? in : out)(res_pos, x)) { assert(false); } } auto res_neg = cld_denominators_negative(n, q, -100); if (res_neg.has_value()) { auto [l, r] = *res_neg; assert(-100 <= l and r <= -1); } for (int x = -100; x <= -1; ++x) { if (not (cld(n, x) == q ? in : out)(res_neg, x)) { assert(false); } } } void fld_test(int n, int q) { auto res_pos = fld_denominators_positive(n, q, 100); if (res_pos.has_value()) { auto [l, r] = *res_pos; assert(1 <= l and r <= 100); } for (int x = 1; x <= 100; ++x) { if (not (fld(n, x) == q ? in : out)(res_pos, x)) { assert(false); } } auto res_neg = fld_denominators_negative(n, q, -100); if (res_neg.has_value()) { auto [l, r] = *res_neg; assert(-100 <= l and r <= -1); } for (int x = -100; x <= -1; ++x) { if (not (fld(n, x) == q ? in : out)(res_neg, x)) { assert(false); } } } int main() { for (int n = -100; n <= 100; ++n) { for (int q = -101; q <= 101; ++q) { cld_test(n, q); fld_test(n, q); } } std::cout << "Hello World" << std::endl; return 0; }
#line 1 "test/src/number/find_denominators/dummy.test.cpp" #define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A" #include <cassert> #include <iostream> #line 1 "library/number/find_denominators.hpp" #include <limits> #include <optional> #include <type_traits> namespace suisen { /** * @brief Calculates { min S, max S }, where S = { x>0 | floor(n/x)=q } in O(1) time. * @tparam T integer type * @param n numerator * @param q quotient (round down) * @param max_val upper bound (closed) * @return { min S, max S } if S is not empty, otherwise std::nullopt */ template <typename T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr> std::optional<std::pair<T, T>> fld_denominators_positive(T n, T q, T max_val = std::numeric_limits<T>::max()) { T l, r; if (q >= 0) { if (n < 0) return std::nullopt; // cld(n + 1, q + 1) <= x <= fld(n, q) l = (n + 1 + q) / (q + 1), r = q == 0 ? max_val : std::min(max_val, n / q); } else { if (n >= 0) return std::nullopt; // cld(n, q) <= x <= fld(n + 1, q + 1) l = (n + q + 1) / q, r = q == -1 ? max_val : std::min(max_val, (n + 1) / (q + 1)); } if (l <= r) return std::make_pair(l, r); else return std::nullopt; } /** * @brief Calculates { min S, max S }, where S = { x<0 | floor(n/x)=q } in O(1) time. * @tparam T integer type * @param n numerator * @param q quotient (round down) * @param min_val lower bound (closed) * @return { min S, max S } if S is not empty, otherwise std::nullopt */ template <typename T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr> std::optional<std::pair<T, T>> fld_denominators_negative(T n, T q, T min_val = std::numeric_limits<T>::min()) { T l, r; if (q >= 0) { if (n > 0) return std::nullopt; // cld(n, q) <= x <= fld(n - 1, q + 1) l = q == 0 ? min_val : std::max(min_val, n / q), r = (n - 1 - q) / (q + 1); } else { if (n <= 0) return std::nullopt; // cld(n - 1, q + 1) <= x <= fld(n, q) l = q == -1 ? min_val : std::max(min_val, (n - 1) / (q + 1)), r = (n - q - 1) / q; } if (l <= r) return std::make_pair(l, r); else return std::nullopt; } /** * @brief Calculates { min S, max S }, where S = { x>0 | ceil(n/x)=q } in O(1) time. * @tparam T integer type * @param n numerator * @param q quotient (round down) * @param max_val upper bound (closed) * @return { min S, max S } if S is not empty, otherwise std::nullopt */ template <typename T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr> std::optional<std::pair<T, T>> cld_denominators_positive(T n, T q, T max_val = std::numeric_limits<T>::max()) { T l, r; if (q > 0) { if (n <= 0) return std::nullopt; l = (n + q - 1) / q, r = q == 1 ? max_val : std::min(max_val, (n - 1) / (q - 1)); } else { if (n > 0) return std::nullopt; l = (n - 1 + q) / (q - 1), r = q == 0 ? max_val : std::min(max_val, n / q); } if (l <= r) return std::make_pair(l, r); else return std::nullopt; } /** * @brief Calculates { min S, max S }, where S = { x<0 | ceil(n/x)=q } in O(1) time. * @tparam T integer type * @param n numerator * @param q quotient (round down) * @param min_val lower bound (closed) * @return { min S, max S } if S is not empty, otherwise std::nullopt */ template <typename T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr> std::optional<std::pair<T, T>> cld_denominators_negative(T n, T q, T min_val = std::numeric_limits<T>::min()) { T l, r; if (q > 0) { if (n >= 0) return std::nullopt; l = q == 1 ? min_val : std::max(min_val, (n + 1) / (q - 1)), r = (n - q + 1) / q; } else { if (n < 0) return std::nullopt; l = q == 0 ? min_val : std::max(min_val, n / q), r = (n + 1 - q) / (q - 1); } if (l <= r) return std::make_pair(l, r); else return std::nullopt; } } // namespace suisen #line 7 "test/src/number/find_denominators/dummy.test.cpp" using suisen::fld_denominators_positive; using suisen::fld_denominators_negative; using suisen::cld_denominators_positive; using suisen::cld_denominators_negative; template <typename T> constexpr inline int pow_m1(T n) { return -(n & 1) | 1; } template <> constexpr inline int pow_m1<bool>(bool n) { return -int(n) | 1; } template <typename T> constexpr inline T fld(const T x, const T y) { return (x ^ y) >= 0 ? x / y : (x - (y + pow_m1(y >= 0))) / y; } template <typename T> constexpr inline T cld(const T x, const T y) { return (x ^ y) <= 0 ? x / y : (x + (y + pow_m1(y >= 0))) / y; } bool in(const std::optional<std::pair<int, int>> &r, int x) { return r.has_value() and r->first <= x and x <= r->second; } bool out(const std::optional<std::pair<int, int>> &r, int x) { return not r.has_value() or x < r->first or x > r->second; } void cld_test(int n, int q) { auto res_pos = cld_denominators_positive(n, q, 100); if (res_pos.has_value()) { auto [l, r] = *res_pos; assert(1 <= l and r <= 100); } for (int x = 1; x <= 100; ++x) { if (not (cld(n, x) == q ? in : out)(res_pos, x)) { assert(false); } } auto res_neg = cld_denominators_negative(n, q, -100); if (res_neg.has_value()) { auto [l, r] = *res_neg; assert(-100 <= l and r <= -1); } for (int x = -100; x <= -1; ++x) { if (not (cld(n, x) == q ? in : out)(res_neg, x)) { assert(false); } } } void fld_test(int n, int q) { auto res_pos = fld_denominators_positive(n, q, 100); if (res_pos.has_value()) { auto [l, r] = *res_pos; assert(1 <= l and r <= 100); } for (int x = 1; x <= 100; ++x) { if (not (fld(n, x) == q ? in : out)(res_pos, x)) { assert(false); } } auto res_neg = fld_denominators_negative(n, q, -100); if (res_neg.has_value()) { auto [l, r] = *res_neg; assert(-100 <= l and r <= -1); } for (int x = -100; x <= -1; ++x) { if (not (fld(n, x) == q ? in : out)(res_neg, x)) { assert(false); } } } int main() { for (int n = -100; n <= 100; ++n) { for (int q = -101; q <= 101; ++q) { cld_test(n, q); fld_test(n, q); } } std::cout << "Hello World" << std::endl; return 0; }