メモの日々


2019年06月22日(土) [長年日記]

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

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

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

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

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

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

#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} \]

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