C++ Library for Competitive Programming
/*
* @title 数学/拡張 Euclid の互除法
*
* verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_E
*/
#include <iostream>
#include "emthrm/math/ext_gcd.hpp"
int main() {
int a, b;
std::cin >> a >> b;
const auto [x, y] = emthrm::ext_gcd(a, b);
std::cout << x << ' ' << y << '\n';
return 0;
}
#line 1 "test/math/ext_gcd.test.cpp"
/*
* @title 数学/拡張 Euclid の互除法
*
* verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_E
*/
#include <iostream>
#line 1 "include/emthrm/math/ext_gcd.hpp"
#include <tuple>
#include <utility>
namespace emthrm {
template <typename T>
std::pair<T, T> ext_gcd(T a, T b) {
T x = 1, y = 0;
for (T u = 0, v = 1; b;) {
const T q = a / b;
std::swap(a -= q * b, b);
std::swap(x -= q * u, u);
std::swap(y -= q * v, v);
}
return a < 0 ? std::make_pair(-x, -y) : std::make_pair(x, y);
}
} // namespace emthrm
#line 10 "test/math/ext_gcd.test.cpp"
int main() {
int a, b;
std::cin >> a >> b;
const auto [x, y] = emthrm::ext_gcd(a, b);
std::cout << x << ' ' << y << '\n';
return 0;
}