Library
This documentation is automatically generated by online-judge-tools/verification-helper
test/aizu-online-judge/NTL_1_E.test.cpp
- View this file on GitHub
- Last update: 2022-04-06 15:02:09+09:00
- Problem: https://onlinejudge.u-aizu.ac.jp/problems/NTL_1_E
Depends on
- Extended Euclidean Algorithm
(src/number_theory/ext_gcd.hpp)
- Output Stream
(src/utils/io/ostream.hpp)
- SFINAE
(src/utils/sfinae.hpp)
Code
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/NTL_1_E"
#include <iostream>
#include "src/number_theory/ext_gcd.hpp"
#include "src/utils/io/ostream.hpp"
int main() {
using namespace workspace;
int a, b;
std::cin >> a >> b;
__int128_t _a = a;
auto [x, y] = ext_gcd(_a, b);
if (x > 0) x -= b, y += a;
if ((y - x) * 2 > a + b) x += b, y -= a;
a = x, b = y;
std::cout << std::tie(a, b) << "\n";
}#line 1 "test/aizu-online-judge/NTL_1_E.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/NTL_1_E"
#include <iostream>
#line 2 "src/number_theory/ext_gcd.hpp"
/**
* @file ext_gcd.hpp
* @brief Extended Euclidean Algorithm
*/
#include <tuple>
#line 2 "src/utils/sfinae.hpp"
/**
* @file sfinae.hpp
* @brief SFINAE
*/
#include <cstdint>
#include <iterator>
#include <type_traits>
#ifndef __INT128_DEFINED__
#ifdef __SIZEOF_INT128__
#define __INT128_DEFINED__ 1
#else
#define __INT128_DEFINED__ 0
#endif
#endif
namespace std {
#if __INT128_DEFINED__
template <> struct make_signed<__uint128_t> { using type = __int128_t; };
template <> struct make_signed<__int128_t> { using type = __int128_t; };
template <> struct make_unsigned<__uint128_t> { using type = __uint128_t; };
template <> struct make_unsigned<__int128_t> { using type = __uint128_t; };
template <> struct is_signed<__uint128_t> : std::false_type {};
template <> struct is_signed<__int128_t> : std::true_type {};
template <> struct is_unsigned<__uint128_t> : std::true_type {};
template <> struct is_unsigned<__int128_t> : std::false_type {};
#endif
} // namespace std
namespace workspace {
template <class Tp, class... Args> struct variadic_front { using type = Tp; };
template <class... Args> struct variadic_back;
template <class Tp> struct variadic_back<Tp> { using type = Tp; };
template <class Tp, class... Args> struct variadic_back<Tp, Args...> {
using type = typename variadic_back<Args...>::type;
};
template <class type, template <class> class trait>
using enable_if_trait_type = typename std::enable_if<trait<type>::value>::type;
/**
* @brief Return type of subscripting ( @c [] ) access.
*/
template <class _Tp>
using subscripted_type =
typename std::decay<decltype(std::declval<_Tp&>()[0])>::type;
template <class Container>
using element_type = typename std::decay<decltype(*std::begin(
std::declval<Container&>()))>::type;
template <class _Tp, class = void> struct has_begin : std::false_type {};
template <class _Tp>
struct has_begin<
_Tp, std::__void_t<decltype(std::begin(std::declval<const _Tp&>()))>>
: std::true_type {
using type = decltype(std::begin(std::declval<const _Tp&>()));
};
template <class _Tp, class = void> struct has_size : std::false_type {};
template <class _Tp>
struct has_size<_Tp, std::__void_t<decltype(std::size(std::declval<_Tp>()))>>
: std::true_type {};
template <class _Tp, class = void> struct has_resize : std::false_type {};
template <class _Tp>
struct has_resize<_Tp, std::__void_t<decltype(std::declval<_Tp>().resize(
std::declval<size_t>()))>> : std::true_type {};
template <class _Tp, class = void> struct has_mod : std::false_type {};
template <class _Tp>
struct has_mod<_Tp, std::__void_t<decltype(_Tp::mod)>> : std::true_type {};
template <class _Tp, class = void> struct is_integral_ext : std::false_type {};
template <class _Tp>
struct is_integral_ext<
_Tp, typename std::enable_if<std::is_integral<_Tp>::value>::type>
: std::true_type {};
#if __INT128_DEFINED__
template <> struct is_integral_ext<__int128_t> : std::true_type {};
template <> struct is_integral_ext<__uint128_t> : std::true_type {};
#endif
#if __cplusplus >= 201402
template <class _Tp>
constexpr static bool is_integral_ext_v = is_integral_ext<_Tp>::value;
#endif
template <typename _Tp, typename = void> struct multiplicable_uint {
using type = uint_least32_t;
};
template <typename _Tp>
struct multiplicable_uint<
_Tp,
typename std::enable_if<(2 < sizeof(_Tp)) &&
(!__INT128_DEFINED__ || sizeof(_Tp) <= 4)>::type> {
using type = uint_least64_t;
};
#if __INT128_DEFINED__
template <typename _Tp>
struct multiplicable_uint<_Tp,
typename std::enable_if<(4 < sizeof(_Tp))>::type> {
using type = __uint128_t;
};
#endif
template <typename _Tp> struct multiplicable_int {
using type =
typename std::make_signed<typename multiplicable_uint<_Tp>::type>::type;
};
template <typename _Tp> struct multiplicable {
using type = std::conditional_t<
is_integral_ext<_Tp>::value,
std::conditional_t<std::is_signed<_Tp>::value,
typename multiplicable_int<_Tp>::type,
typename multiplicable_uint<_Tp>::type>,
_Tp>;
};
template <class> struct first_arg { using type = void; };
template <class _R, class _Tp, class... _Args>
struct first_arg<_R(_Tp, _Args...)> {
using type = _Tp;
};
template <class _R, class _Tp, class... _Args>
struct first_arg<_R (*)(_Tp, _Args...)> {
using type = _Tp;
};
template <class _G, class _R, class _Tp, class... _Args>
struct first_arg<_R (_G::*)(_Tp, _Args...)> {
using type = _Tp;
};
template <class _G, class _R, class _Tp, class... _Args>
struct first_arg<_R (_G::*)(_Tp, _Args...) const> {
using type = _Tp;
};
template <class _Tp, class = void> struct parse_compare : first_arg<_Tp> {};
template <class _Tp>
struct parse_compare<_Tp, std::__void_t<decltype(&_Tp::operator())>>
: first_arg<decltype(&_Tp::operator())> {};
template <class _Container, class = void> struct get_dimension {
static constexpr size_t value = 0;
};
template <class _Container>
struct get_dimension<_Container,
std::enable_if_t<has_begin<_Container>::value>> {
static constexpr size_t value =
1 + get_dimension<typename std::iterator_traits<
typename has_begin<_Container>::type>::value_type>::value;
};
} // namespace workspace
#line 11 "src/number_theory/ext_gcd.hpp"
namespace workspace {
/**
* @param __a Integer
* @param __b Integer
* @return Pair of integers (x, y) s.t. ax + by = g = gcd(a, b) and (b = 0 or 0
* <= x < |b/g|) and (a = 0 or -|a/g| < y <= 0). Return (0, 0) if (a, b) = (0,
* 0).
*/
template <typename _T1, typename _T2>
constexpr auto ext_gcd(_T1 __a, _T2 __b) noexcept {
static_assert(is_integral_ext<_T1>::value);
static_assert(is_integral_ext<_T2>::value);
using value_type = typename std::make_signed<
typename std::common_type<_T1, _T2>::type>::type;
using result_type = std::pair<value_type, value_type>;
value_type a{__a}, b{__b}, p{1}, q{}, r{}, s{1};
while (b != value_type(0)) {
auto t = a / b;
r ^= p ^= r ^= p -= t * r;
s ^= q ^= s ^= q -= t * s;
b ^= a ^= b ^= a -= t * b;
}
if (a < 0) p = -p, q = -q, a = -a;
if (p < 0) {
__a /= a, __b /= a;
if (__b > 0)
p += __b, q -= __a;
else
p -= __b, q += __a;
}
return result_type{p, q};
}
/**
* @param __a Integer
* @param __b Integer
* @param __c Integer
* @return Pair of integers (x, y) s.t. ax + by = c and (b = 0 or 0 <= x <
* |b/g|). Return (0, 0) if there is no solution.
*/
template <typename _T1, typename _T2, typename _T3>
constexpr auto ext_gcd(_T1 __a, _T2 __b, _T3 __c) noexcept {
static_assert(is_integral_ext<_T1>::value);
static_assert(is_integral_ext<_T2>::value);
static_assert(is_integral_ext<_T3>::value);
using value_type = typename std::make_signed<
typename std::common_type<_T1, _T2, _T3>::type>::type;
using result_type = std::pair<value_type, value_type>;
value_type a{__a}, b{__b}, p{1}, q{}, r{}, s{1};
while (b != value_type(0)) {
auto t = a / b;
r ^= p ^= r ^= p -= t * r;
s ^= q ^= s ^= q -= t * s;
b ^= a ^= b ^= a -= t * b;
}
if (__c % a) return result_type{};
__a /= a, __b /= a, __c /= a;
p *= __c, q *= __c;
if (__b != value_type(0)) {
auto t = p / __b;
p -= __b * t;
q += __a * t;
if (p < 0) {
if (__b > 0)
p += __b, q -= __a;
else
p -= __b, q += __a;
}
}
return result_type{p, q};
}
} // namespace workspace
#line 2 "src/utils/io/ostream.hpp"
/**
* @file ostream.hpp
* @brief Output Stream
*/
#line 9 "src/utils/io/ostream.hpp"
#line 2 "lib/cxx17"
#line 2 "lib/cxx14"
#ifndef _CXX14_CONSTEXPR
#if __cplusplus >= 201402L
#define _CXX14_CONSTEXPR constexpr
#else
#define _CXX14_CONSTEXPR
#endif
#endif
#line 4 "lib/cxx17"
#ifndef _CXX17_CONSTEXPR
#if __cplusplus >= 201703L
#define _CXX17_CONSTEXPR constexpr
#else
#define _CXX17_CONSTEXPR
#endif
#endif
#ifndef _CXX17_STATIC_ASSERT
#if __cplusplus >= 201703L
#define _CXX17_STATIC_ASSERT static_assert
#else
#define _CXX17_STATIC_ASSERT assert
#endif
#endif
#line 22 "lib/cxx17"
#if __cplusplus < 201703L
namespace std {
/**
* @brief Return the size of a container.
* @param __cont Container.
*/
template <typename _Container>
constexpr auto size(const _Container& __cont) noexcept(noexcept(__cont.size()))
-> decltype(__cont.size()) {
return __cont.size();
}
/**
* @brief Return the size of an array.
*/
template <typename _Tp, size_t _Nm>
constexpr size_t size(const _Tp (&)[_Nm]) noexcept {
return _Nm;
}
/**
* @brief Return whether a container is empty.
* @param __cont Container.
*/
template <typename _Container>
[[nodiscard]] constexpr auto empty(const _Container& __cont) noexcept(
noexcept(__cont.empty())) -> decltype(__cont.empty()) {
return __cont.empty();
}
/**
* @brief Return whether an array is empty (always false).
*/
template <typename _Tp, size_t _Nm>
[[nodiscard]] constexpr bool empty(const _Tp (&)[_Nm]) noexcept {
return false;
}
/**
* @brief Return whether an initializer_list is empty.
* @param __il Initializer list.
*/
template <typename _Tp>
[[nodiscard]] constexpr bool empty(initializer_list<_Tp> __il) noexcept {
return __il.size() == 0;
}
struct monostate {};
} // namespace std
#else
#include <variant>
#endif
#line 11 "src/utils/io/ostream.hpp"
namespace workspace {
template <class _Os> struct is_ostream {
template <typename... _Args>
static std::true_type __test(std::basic_ostream<_Args...> *);
static std::false_type __test(void *);
constexpr static bool value = decltype(__test(std::declval<_Os *>()))::value;
};
template <class _Os>
using ostream_ref =
typename std::enable_if<is_ostream<_Os>::value, _Os &>::type;
/**
* @brief Stream insertion operator for C-style array.
*
* @param __os Output stream
* @param __a Array
* @return Reference to __os.
*/
template <class _Os, class _Tp, size_t _Nm>
typename std::enable_if<bool(sizeof(_Tp) > 2), ostream_ref<_Os>>::type
operator<<(_Os &__os, const _Tp (&__a)[_Nm]) {
if _CXX17_CONSTEXPR (_Nm) {
__os << *__a;
for (auto __i = __a + 1, __e = __a + _Nm; __i != __e; ++__i)
__os << ' ' << *__i;
}
return __os;
}
/**
* @brief Stream insertion operator for std::array.
*
* @param __os Output stream
* @param __a Array
* @return Reference to __os.
*/
template <class _Os, class _Tp, size_t _Nm>
ostream_ref<_Os> operator<<(_Os &__os, const std::array<_Tp, _Nm> &__a) {
if _CXX17_CONSTEXPR (_Nm) {
__os << __a[0];
for (size_t __i = 1; __i != _Nm; ++__i) __os << ' ' << __a[__i];
}
return __os;
}
/**
* @brief Stream insertion operator for std::pair.
*
* @param __os Output stream
* @param __p Pair
* @return Reference to __os.
*/
template <class _Os, class _T1, class _T2>
ostream_ref<_Os> operator<<(_Os &__os, const std::pair<_T1, _T2> &__p) {
return __os << __p.first << ' ' << __p.second;
}
/**
* @brief Stream insertion operator for std::tuple.
*
* @param __os Output stream
* @param __t Tuple
* @return Reference to __os.
*/
template <class _Os, class _Tp, size_t _Nm = 0>
typename std::enable_if<bool(std::tuple_size<_Tp>::value + 1),
ostream_ref<_Os>>::type
operator<<(_Os &__os, const _Tp &__t) {
if _CXX17_CONSTEXPR (_Nm != std::tuple_size<_Tp>::value) {
if _CXX17_CONSTEXPR (_Nm) __os << ' ';
__os << std::get<_Nm>(__t);
operator<<<_Os, _Tp, _Nm + 1>(__os, __t);
}
return __os;
}
template <class _Os, class _Container,
typename = decltype(std::begin(std::declval<_Container>()))>
typename std::enable_if<
!std::is_convertible<std::decay_t<_Container>, std::string>::value &&
!std::is_convertible<std::decay_t<_Container>, char *>::value,
ostream_ref<_Os>>::type
operator<<(_Os &__os, const _Container &__cont) {
bool __h = true;
for (auto &&__e : __cont) __h ? __h = 0 : (__os << ' ', 0), __os << __e;
return __os;
}
#ifdef __SIZEOF_INT128__
/**
* @brief Stream insertion operator for __int128_t.
*
* @param __os Output Stream
* @param __x 128-bit integer
* @return Reference to __os.
*/
template <class _Os> ostream_ref<_Os> operator<<(_Os &__os, __int128_t __x) {
if (!__x) return __os << '0';
if (__x < 0) __os << '-';
char __s[40], *__p = __s;
while (__x) {
auto __d = __x % 10;
*__p++ = '0' + (__x < 0 ? -__d : __d);
__x /= 10;
}
*__p = 0;
for (char *__t = __s; __t < --__p; ++__t) *__t ^= *__p ^= *__t ^= *__p;
return __os << __s;
}
/**
* @brief Stream insertion operator for __uint128_t.
*
* @param __os Output Stream
* @param __x 128-bit unsigned integer
* @return Reference to __os.
*/
template <class _Os> ostream_ref<_Os> operator<<(_Os &__os, __uint128_t __x) {
if (!__x) return __os << '0';
char __s[40], *__p = __s;
while (__x) *__p++ = '0' + __x % 10, __x /= 10;
*__p = 0;
for (char *__t = __s; __t < --__p; ++__t) *__t ^= *__p ^= *__t ^= *__p;
return __os << __s;
}
#endif
} // namespace workspace
#line 7 "test/aizu-online-judge/NTL_1_E.test.cpp"
int main() {
using namespace workspace;
int a, b;
std::cin >> a >> b;
__int128_t _a = a;
auto [x, y] = ext_gcd(_a, b);
if (x > 0) x -= b, y += a;
if ((y - x) * 2 > a + b) x += b, y -= a;
a = x, b = y;
std::cout << std::tie(a, b) << "\n";
}