• Class / Function / Type

      std::
    • Header file

      <>
    • Other / All

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

    履歴 編集

    function template
    <numeric>

    std::lcm

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

    概要

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

    適格要件

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

    事前条件

    • |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を満たさない場合、オーバーフローにより戻り値が不正になることがある。

    参照

    関連項目

    実装例

    lcm(m,n)=|mn|gcd(m,n)