最大公約数 (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)\)

実装

using ll = long long;

// Euclidean Algorithm
ll gcd(ll m, ll n) {
  ll r = m % n;
  return r ? gcd(n, r) : n;
}

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

戻る