exgcd … 拡張gcd、ax+by=gcd(x,y)となるa,bを求める - Imoのアルゴリズムライブラリ

拡張gcd

説明

x, yを0でない自然数とし，c=gcd(x,y)とする。このとき，ax+by=cとなる整数a,bが存在する。そして，この a,b は実際に計することが出来る。

計算量

O(logN)

使い方

exgcd(a,b,x,y)でaとbの最小公倍数を返し、x,yへ結果を返す。

ソースコード

int exgcd(int a, int b, int &x, int &y) {
  if (!b) return x = 1, y = 0, a;
  int d = exgcd(b, a % b, y, x);
  y -= a / b * x; return d;
}

確認

なし