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

• View this file on GitHub
• Last update: 2022-12-15 22:18:37+09:00
• Include: #include "emthrm/math/ext_gcd.hpp"

$ax + by = \gcd(a, b)$ を満たす整数解 $(x, y)$ を求めるアルゴリズムである。

$ax + by = c \cdot \mathrm{gcd}(a, b)$ の特殊解を $(x, y) = (x^{\prime}, y^{\prime})$ とすると、一般解は $k \in \mathrm{Z}$ を用いて $(x, y) = \left(x^{\prime} + k \frac{b}{\mathrm{gcd}(a, b)}, y^{\prime} - k \frac{a}{\mathrm{gcd}(a, b)}\right)$ と表せる。

時間計算量

$O(\log{\max \lbrace A, B \rbrace})$

仕様

名前	戻り値	備考
template <typename T> std::pair<T, T> ext_gcd(T a, T b);	$ax + by = \gcd(a, b)$ を満たす整数解 $(x, y)$	$a \neq 0,\ b \neq 0$ のとき $\lvert x \rvert \leq \left\lvert \frac{b}{\mathrm{gcd}(a, b)} \right\rvert,\ \lvert y \rvert \leq \left\lvert \frac{a}{\mathrm{gcd}(a, b)} \right\rvert$ が成り立つ。

参考文献

• https://qiita.com/drken/items/b97ff231e43bce50199a
• https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
• https://ja.wikipedia.org/wiki/%E3%83%99%E3%82%BA%E3%83%BC%E3%81%AE%E7%AD%89%E5%BC%8F
• https://scol.hatenablog.com/entry/2019/10/19/180000
• https://divinejk.hatenablog.com/entry/2021/02/28/233332

Submissons

https://onlinejudge.u-aizu.ac.jp/solutions/problem/NTL_1_E/review/5272349/emthrm/C++17

Verified with

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

Code

#ifndef EMTHRM_MATH_EXT_GCD_HPP_
#define 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

#endif  // EMTHRM_MATH_EXT_GCD_HPP_

#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

Back to top page