Extgcd (拡張ユークリッドの互除法) (math/number-theory/extgcd.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-08-10 06:54:42+00:00
• Include: #include "math/number-theory/extgcd.hpp"

extgcd

T extgcd(T a, T b, T &x, T &y)

$\gcd(a, b)$ を返します。$(x, y)$ には $ax + by = \gcd(a, b)$ を満たす整数解が格納されます。整数解は複数考えられますが、$|x| + |y|$ が最小のものが格納されます。

制約

• $1 \leq a, b$

計算量

• $O(\log {\min(a, b)})$

Verified with

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

Code

#pragma once

template <typename T>
T extgcd(T a, 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;
}

#line 2 "math/number-theory/extgcd.hpp"

template <typename T>
T extgcd(T a, 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;
}

Back to top page