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

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

概要

2つの整数 $a, b$ の最大公約数 (GCD: Greatest Common Divisor) を求める．

本実装では「ユークリッドの互除法」を用いており，計算量は $\mathcal{O}(\log(\min(a,b)))$ となる．

参考文献

1. H.H. シルヴァーマン. “第5章 割り切れる関係 —— 整除性と最大公約数”. はじめての数論. 鈴木治郎訳. 原著第4版, 丸善出版, 2022, p.29-33.
2. “最大公約数”. Wikipedia. https://ja.wikipedia.org/wiki/最大公約数.
3. “ユークリッドの互除法”. Wikipedia. https://ja.wikipedia.org/wiki/ユークリッドの互除法.
4. “ユークリッドの互除法の証明と不定方程式”. 高校数学の美しい物語. https://manabitimes.jp/math/672.

Required by

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

Verified with

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

Code

#ifndef ALGORITHM_GREATEST_COMMON_DIVISOR_HPP
#define ALGORITHM_GREATEST_COMMON_DIVISOR_HPP 1

/**
 * @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

#endif

#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

Back to top page