4. lcm

最終更新日時(UTC):
が更新

履歴 編集

function template
<numeric>

std::lcm(C++17)

namespace std {
  template <class M, class N>
  constexpr common_type_t<M, N> lcm(M m, N n);
}

概要

最小公倍数 (least common multiple) を求める。

適格要件

  • 型M および N が bool 以外の整数型であること

事前条件

  • |m| および |n| が common_type_t<M, N> の値として表現できること
  • |m| と |n| の最小公倍数が common_type_t<M, N> の値として表現できること

戻り値

  • m または n が 0 の場合 0 を返す
  • それ以外の場合引数 |m| と |n| の最小公倍数を返す

例外

投げない。

備考

  • この関数は、公式通りに abs(m * n) / gcd(m, n) として実装すると、m * nの箇所でオーバーフローしやすい。実装によっては、式を改良することでオーバーフローしにくいようになっている場合がある
    • GCC (libstdc++), Clang (libc++), Visual C++ : オーバーフローしにくい改良版の式としてabs(m) / gcd(m, n) * abs(n)という実装が使用されている

例

基本的な使い方

#include <cassert>
#include <numeric>

int main() {
  assert(std::lcm(3, 4) == 12);
  assert(std::lcm(4, 3) == 12);

  // コンパイル時に最小公倍数を求めることもできる
  static_assert(std::lcm(0, 1) == 0);
  static_assert(std::lcm(4u, -6l) == 12);
}

出力

オーバーフローしやすい状況の例

#include <iostream>
#include <cstdint>
#include <numeric>

int main() {
  std::uint16_t m = 20000;
  std::uint16_t n = 40000;

  // 標準std::lcm()の動作は実装定義
  std::cout << "std::lcm(" << m << ", " << n << ")     " << std::lcm(m, n) << std::endl;

  // 公式通りのオーバーフローしやすい最小公倍数の実装
  volatile std::uint16_t t = m * n; // 最適化回避のための変数
  std::cout << "formal lcm(" << m << ", " << n << ")   " << (t / std::gcd(m, n)) << std::endl;

  // オーバーフローしにくいよう公式を改良した実装
  auto g = std::gcd(m, n);
  std::cout << "improved lcm(" << m << ", " << n << ") " << m * (n / g) << std::endl;
}

出力例

std::lcm(20000, 40000)     40000
formal lcm(20000, 40000)   0
improved lcm(20000, 40000) 40000

3つ以上の値に対する最小公倍数を求める

#include <cassert>
#include <numeric>
#include <vector>

// 可変引数で最小公倍数を求める関数
template <class T>
T vlcm(T m, T n) {
  return std::lcm(m, n);
}

template <class T, class... Args>
T vlcm(T a, Args... args) {
  return vlcm(a, vlcm(args...));
}

int main() {
  // 2つずつ最小公倍数を求める
  assert(std::lcm(std::lcm(3, 4), 6) == 12);

  // リスト全体の最小公倍数を求める
  std::vector<int> v = {3, 4, 6};
  int r = std::accumulate(v.begin(), v.end(), 1, [](int m, int n) {
    return std::lcm(m, n);
  });
  assert(r == 12);

  // 可変引数で最小公倍数を求める
  assert(vlcm(3, 4, 6) == 12);
}

出力

バージョン

言語

  • C++17

処理系

備考

Clang (libc++)

  • 事前条件を満たすかどうかチェックしない。
  • _LIBCPP_DEBUG マクロが0 以上の場合、事前条件2を満たさなければ abort する。
    • ただしバージョン 4 系では <limits> を <numeric> より先に include しなければならない。
    • それ以外の場合（デフォルト）、オーバーフローにより戻り値が不正になることがある。

GCC (libstdc++)

  • 事前条件を満たすかどうかチェックしない。
  • 事前条件2を満たさない場合、オーバーフローにより戻り値が不正になることがある。

参照

関連項目

実装例

$$ \mathrm{lcm}(m, n) = \frac{|mn|}{\mathrm{gcd}(m, n)} $$