最大公約数 (greatest common divisor, GCD)

概要

2つの数 \(a, b\) について、\(a = a'g\), \(b = b'g\) (\(a', b'\) は互いに素)となるような\(g = gcd(a, b)\)を計算する。

拡張されたGCDでは、 \(ax + by = g\) となるような \(x, y, g\) を計算する。

また、最小公倍数(least common multiple, LCM)は \(\displaystyle \frac{ab}{gcd(a, b)}\) で計算する。

計算量

\(N = \max(a, b)\) とすると \(O(\log N)\)

実装

// gcd(greatest common divisor)
ll gcd(ll m, ll n) {
  ll r = m % n;
  return r ? gcd(n, r) : n;
}

// extgcd(a, b, x, y)
// -> a*x + b*y = d を満たす
ll extgcd(ll a, ll b, ll &x, ll &y) {
  if(b) {
    d = extgcd(b, a%b, y, x);
    y -= (a/b)*x;
    return d;
  }
  x = 1; y = 0;
  return a;
}