test/aoj/ntl-1-e.test.cpp

View this file on GitHub
Last update: 2026-10-13 01:32:37+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_E

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_E"

#include <iostream>

#include "../../src/base/functions.hpp"

int main() {
    long long a, b;
    std::cin >> a >> b;
    long long x, y;
    // extgcd の解は |x| + |y| が最小で、同じなら x <= y を満たす (問題が要求する解と一致する)
    extgcd(a, b, x, y);
    std::cout << x << ' ' << y << '\n';
}

#line 1 "test/aoj/ntl-1-e.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_E"

#include <iostream>

#line 2 "src/base/functions.hpp"

/**
 * @file functions.hpp
 * @brief 汎用関数 (chmin, chmax, 二分探索など)
 */

#include <algorithm>
#include <array>
#include <cmath>
#include <numeric>
#line 2 "src/base/traits.hpp"

/**
 * @file traits.hpp
 * @brief 型特性
 */

#include <cstddef>
#include <iterator>
#include <set>
#include <type_traits>
#include <utility>

namespace detail {
using std::begin, std::end;

template <class T, class = void>
struct is_range_impl : std::false_type {};
template <class T>
struct is_range_impl<T, std::void_t<decltype(begin(std::declval<T&>()), end(std::declval<T&>()))>> : std::true_type {};
}  // namespace detail

template <class T>
struct is_range : detail::is_range_impl<T>::type {};
template <class T>
inline constexpr bool is_range_v = is_range<T>::value;

#define HAS_METHOD(func_name)                                                              \
    namespace detail {                                                                     \
    template <class T, class = void>                                                       \
    struct has_##func_name##_impl : std::false_type {};                                    \
    template <class T>                                                                     \
    struct has_##func_name##_impl<T, std::void_t<decltype(std::declval<T>().func_name())>> \
        : std::true_type {};                                                               \
    }                                                                                      \
    template <class T>                                                                     \
    struct has_##func_name : detail::has_##func_name##_impl<T>::type {};                   \
    template <class T>                                                                     \
    inline constexpr bool has_##func_name##_v = has_##func_name<T>::value;

#define HAS_METHOD_ARG(func_name)                                                                              \
    namespace detail {                                                                                         \
    template <class T, typename U, class = void>                                                               \
    struct has_##func_name##_impl : std::false_type {};                                                        \
    template <class T, typename U>                                                                             \
    struct has_##func_name##_impl<T, U, std::void_t<decltype(std::declval<T>().func_name(std::declval<U>()))>> \
        : std::true_type {};                                                                                   \
    }                                                                                                          \
    template <class T, typename U>                                                                             \
    struct has_##func_name : detail::has_##func_name##_impl<T, U>::type {};                                    \
    template <class T, typename U>                                                                             \
    inline constexpr bool has_##func_name##_v = has_##func_name<T, U>::value;

HAS_METHOD(repr)
HAS_METHOD(type_str)
HAS_METHOD(initializer_str)
HAS_METHOD(max)
HAS_METHOD(min)
HAS_METHOD(reversed)
HAS_METHOD(sorted)
HAS_METHOD(sum)
HAS_METHOD(product)
HAS_METHOD(product_xor)
HAS_METHOD_ARG(count)
HAS_METHOD_ARG(find)
HAS_METHOD_ARG(lower_bound)
HAS_METHOD_ARG(upper_bound)

#define ENABLE_IF_T_IMPL(expr) std::enable_if_t<expr, std::nullptr_t> = nullptr
#define ENABLE_IF_T(...) ENABLE_IF_T_IMPL((__VA_ARGS__))

template <class C>
using mem_value_type = typename C::value_type;
template <class C>
using mem_difference_type = typename C::difference_type;

namespace detail {
template <class T, class = void>
struct is_sorted_container_impl : std::false_type {};
template <class T>
struct is_sorted_container_impl<std::set<T>> : std::true_type {};
template <class T>
struct is_sorted_container_impl<std::multiset<T>> : std::true_type {};
}  // namespace detail
template <class T>
struct is_sorted_container : detail::is_sorted_container_impl<T>::type {};
template <class T>
inline constexpr bool is_sorted_container_v = is_sorted_container<T>::value;
#line 13 "src/base/functions.hpp"

template <typename T1, typename T2>
inline constexpr bool chmin(T1 &a, T2 b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template <typename T1, typename T2>
inline constexpr bool chmax(T1 &a, T2 b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

inline constexpr long long max(const long long &t1, const long long &t2) {
    return std::max<long long>(t1, t2);
}

inline constexpr long long min(const long long &t1, const long long &t2) {
    return std::min<long long>(t1, t2);
}

using std::abs;
using std::gcd;
using std::lcm;
using std::size;

template <typename T>
constexpr T extgcd(const T &a, const T &b, T &x, T &y) {
    T d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1;
        y = 0;
    }
    return d;
}

/**
 * 偏角ソート
 * 反時計回り
 * x 軸正方向を始点とし、零ベクトルは x 軸正方向と同じ偏角として扱う
 */
template <typename T, ENABLE_IF_T(std::is_integral_v<T>)>
bool argcmp(std::array<T, 2> a, std::array<T, 2> b) {
    // 零ベクトルは外積で比べられないので、偏角 0 (x 軸正方向) として先に判定する
    const bool a_zero = a[0] == 0 && a[1] == 0;
    const bool b_zero = b[0] == 0 && b[1] == 0;
    if (b_zero) return false;  // 偏角 0 より小さいものはない
    if (a_zero) return !(b[1] == 0 && b[0] > 0);  // b の偏角が 0 より大きいか
    T a0 = std::array<T, 2>{a[1], a[0]} < std::array<T, 2>{0, 0};
    T b0 = std::array<T, 2>{b[1], b[0]} < std::array<T, 2>{0, 0};
    if (a0 < b0) {
        return true;
    } else if (b0 < a0) {
        return false;
    } else {
        return b[0] * a[1] < a[0] * b[1];
    }
}

template <typename M, typename N, class F, ENABLE_IF_T(std::is_integral_v<std::common_type_t<M, N>> and std::is_invocable_r_v<bool, F, std::common_type_t<M, N>>)>
inline constexpr std::common_type_t<M, N> binary_search(const M &ok, const N &ng, F f) {
    std::common_type_t<M, N> _ok = ok, _ng = ng;
    while (std::abs(_ok - _ng) > 1) {
        std::common_type_t<M, N> mid = (_ok + _ng) / 2;
        if (f(mid)) {
            _ok = mid;
        } else {
            _ng = mid;
        }
    }
    return _ok;
}

template <typename M, typename N, class F, ENABLE_IF_T(not std::is_integral_v<std::common_type_t<M, N>> and std::is_invocable_r_v<bool, F, std::common_type_t<M, N>>)>
inline constexpr std::common_type_t<M, N> binary_search(const M &ok, const N &ng, F f) {
    std::common_type_t<M, N> _ok = ok, _ng = ng;
    for (int i = 0; i < 100; i++) {
        std::common_type_t<M, N> mid = (_ok + _ng) / 2;
        if (f(mid)) {
            _ok = mid;
        } else {
            _ng = mid;
        }
    }
    return _ok;
}

/**
 * 0 <= x < a
 */
inline constexpr bool inrange(long long x, long long a) {
    return 0 <= x and x < a;
}
/**
 * a <= x < b
 */
inline constexpr bool inrange(long long x, long long a, long long b) {
    return a <= x and x < b;
}
/**
 * 0 <= x < a and 0 <= y < b
 */
inline constexpr bool inrect(long long x, long long y, long long a, long long b) {
    return 0 <= x and x < a and 0 <= y and y < b;
}
#line 6 "test/aoj/ntl-1-e.test.cpp"

int main() {
    long long a, b;
    std::cin >> a >> b;
    long long x, y;
    // extgcd の解は |x| + |y| が最小で、同じなら x <= y を満たす (問題が要求する解と一致する)
    extgcd(a, b, x, y);
    std::cout << x << ' ' << y << '\n';
}