最終更新日時(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) を求める。

要件

  1. M および Nbool 以外の整数型であること
    満足しない場合プログラムは不適格となる
  2. |m| および |n|common_type_t<M, N> の値として表現できること
    満足しない場合の挙動は未定義
  3. |m||n| の最小公倍数が common_type_t<M, N> の値として表現できること
    満足しない場合の挙動は未定義

戻り値

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

例外

投げない。

#include <cmath>
#include <iostream>
#include <limits>
#include <numeric>

int main() {
  static_assert(std::lcm(0, 1) == 0);
  static_assert(std::lcm(4u, -6l) == 12);

  // オーバーフローする例
  auto m = std::numeric_limits<uint32_t>::max();
  auto n = m - 1;
  std::cout << "lcm(" << m << ", " << n << ")      " << std::lcm(m, n) << std::endl;
  auto g = std::gcd(m, n);  // 1
  std::cout << "true lcm(" << m << ", " << n << ") " << std::fabs(m) * std::fabs(n / g) << std::endl;
}

出力例

lcm(4294967295, 4294967294)      2
true lcm(4294967295, 4294967294) 1.84467e+19

バージョン

言語

  • C++17

処理系

備考

Clang (libc++)

要件 2 を満たすかどうかチェックしない。

_LIBCPP_DEBUG マクロが 0 以上の場合、要件 3 を満たさなければ abort する。 ただし 4 系では <limits><numeric> より先に include しなければならない。 それ以外の場合(デフォルト)、オーバーフローにより戻り値が不正になることがある。

GCC (libstdc++)

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

参照

関連項目

実装例

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