説明

$ax+by=\gcd(a,b)$ なる $x,y$ をユークリッドの互除法の過程から計算する．

計算量

  • $O(\log N)$

実装例

  • extgcd($a$, $b$, $x$, $y$): $a$ と $b$ の最大公約数を返す。 $x, y$ には $ax+by=\gcd(a, b)$ なる $x, y$ が格納される。
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;
}

検証

AOJ NTL_1_E 拡張ユークリッドの互除法

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_E"

#include "../../template/template.cpp"

#include "../extgcd.cpp"

int main() {
  int a, b, x, y;
  cin >> a >> b;
  extgcd(a, b, x, y);
  cout << x << " " << y << endl;
}