数学/拡張 Euclid の互除法
(test/math/ext_gcd.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 01:48:23+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_E

Depends on

• 拡張 Euclid の互除法 (extended Euclidean algorithm) (include/emthrm/math/ext_gcd.hpp)

Code

/*
 * @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;
}

Back to top page