gcd … 最小公倍数 - Imoのアルゴリズムライブラリ

最小公倍数

説明

2 つの自然数（または整式） a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。
これをユークリッドの互除法と言う。

計算量

O(logN)

使い方

gcd(a,b)でaとbの最小公倍数を返す

ソースコード

int gcd(int a, int b) {
  return b ? gcd(b, a % b) : a;
}

template版

template<class t> t gcd(t a, t b) { return b != 0 ? gcd(b, a % b) : a; }

確認

なし