Least Common Multiple（最小公倍数）
(algorithm/Math/NumberTheory/least_common_multiple.hpp)

• View this file on GitHub
• Last update: 2025-07-03 00:41:25+09:00
• Include: #include "algorithm/Math/NumberTheory/least_common_multiple.hpp"

概要

2つの整数 $a, b$ の最小公倍数 (LCM: Least Common Multiple) を求める．

以下の等式が成り立つため，$a$ と $b$ の最大公約数が分かればよい．

\[\begin{align} &\operatorname{lcm}(a,b) \times \gcd(a,b) = a \times b \notag\\ &\Leftrightarrow \operatorname{lcm}(a,b) = \frac{a \times b}{\gcd(a,b)} \notag \end{align}\]

アルゴリズムの計算量は，最大公約数を求めるところがボトルネックとなり，$\mathcal{O}(\log(\min(a,b)))$ となる．

参考文献

1. “最小公倍数”. Wikipedia. https://ja.wikipedia.org/wiki/最小公倍数.

Depends on

• Greatest Common Divisor（最大公約数） (algorithm/Math/NumberTheory/greatest_common_divisor.hpp)

Verified with

• verify/aoj-NTL_1_C-least_common_multiple.test.cpp

Code

#ifndef ALGORITHM_LEAST_COMMON_MULTIPLE_HPP
#define ALGORITHM_LEAST_COMMON_MULTIPLE_HPP 1

/**
 * @brief Least Common Multiple（最小公倍数）
 * @docs docs/Math/NumberTheory/least_common_multiple.md
 */

#include "greatest_common_divisor.hpp"

namespace algorithm {

template <typename Type>
constexpr Type ilcm(Type a, Type b) { return a / igcd(a, b) * b; }

}  // namespace algorithm

#endif

#line 1 "algorithm/Math/NumberTheory/least_common_multiple.hpp"



/**
 * @brief Least Common Multiple（最小公倍数）
 * @docs docs/Math/NumberTheory/least_common_multiple.md
 */

#line 1 "algorithm/Math/NumberTheory/greatest_common_divisor.hpp"



/**
 * @brief Greatest Common Divisor（最大公約数）
 * @docs docs/Math/NumberTheory/greatest_common_divisor.md
 */

namespace algorithm {

template <typename Type>
constexpr Type igcd(Type a, Type b) { return (b == 0 ? a : igcd(b, a % b)); }

}  // namespace algorithm


#line 10 "algorithm/Math/NumberTheory/least_common_multiple.hpp"

namespace algorithm {

template <typename Type>
constexpr Type ilcm(Type a, Type b) { return a / igcd(a, b) * b; }

}  // namespace algorithm

Back to top page