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)
という実装が使用されている
- GCC (libstdc++), Clang (libc++), Visual C++ : オーバーフローしにくい改良版の式として
例
基本的な使い方
#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);
}
12
#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;
}
20
#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);
}
30
int r = std::accumulate(v.begin(), v.end(), 1, [](int m, int n) {
#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);
出力
バージョン
言語
- C++17
処理系
- Clang: 4.0.0 ✅
- GCC: 7.1.0 ✅
- ICC: ??
- Visual C++: ??
備考
Clang (libc++)
- 事前条件を満たすかどうかチェックしない。
_LIBCPP_DEBUG
マクロが0
以上の場合、事前条件2を満たさなければabort
する。- ただしバージョン 4 系では
<limits>
を<numeric>
より先に include しなければならない。 - それ以外の場合(デフォルト)、オーバーフローにより戻り値が不正になることがある。
- ただしバージョン 4 系では
GCC (libstdc++)
- 事前条件を満たすかどうかチェックしない。
- 事前条件2を満たさない場合、オーバーフローにより戻り値が不正になることがある。
参照
- WG21 N3845 Greatest Common Divisor and Least Common Multiple
- WG21 N3913 Greatest Common Divisor and Least Common Multiple, v2
- WG21 N4061 Greatest Common Divisor and Least Common Multiple, v3
- WG21 P0295R0 Adopt Selected Library Fundamentals V2 Components for C++17
- LWG Issue 2837.
gcd
andlcm
should support a wider range of input values - LWG Issue 2759.
gcd
/lcm
andbool
for the WP