メモの日々

■ [c++][math] 最大公約数を求めるコード

最大公約数を求めるC++のコードをメモ。

最大公約数はユークリッドの互除法で計算できる。これは、自然数a1とa2に対して

• a1をa2で割った余りをa3とする。a3が0ならa2が最大公約数。
• a2をa3で割った余りをa4とする。a4が0ならa3が最大公約数。
• ...

という風にしていって求める方法。a1 < a2 であっても問題なく適用できる。また、負の数に対しても絶対値を取れば適用できる。

• 「ユークリッドの互除法」を原始的な方法から1歩ずつ改良 (Qiita)

で色々説明されていて参考になる。

#include <cassert>
#include <iostream>

// Greatest Common Divisor
// a < b でも問題ないことに注意。
template<typename T>
T gcd(T a, T b)
{
  if (a < 0) a = -a;
  if (b < 0) b = -b;
  while (b) {
    const auto r = a % b;
    a = b;
    b = r;
  }
  return a;
}

int main()
{
  assert(gcd(1071, 1029) == 21);
  assert(gcd(1029, 1071) == 21);
  assert(gcd(-1029, -1071) == 21);
  assert(gcd(0, 1071) == 1071);
  assert(gcd(0, 0) == 0);
  assert(gcd(10, 5) == 5);
  assert(gcd(5, 10) == 5);
}

■ [math] 最小公倍数の求め方

aとbの最小公倍数LCMは、最大公約数GCDを用いて

\[ \ LCM = \frac{a \cdot b}{GCD} \]

で求まるということをメモ。