Luzhiled's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ei1333/library

:heavy_check_mark: Extgcd(拡張ユークリッドの互除法)
(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|$ が最小のものが格納されます。

制約

計算量

Verified with

Code

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 1 "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