拡張ユークリッドの互除法
(algorithm/Math/NumberTheory/extgcd.hpp)

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

概要

2つの整数 $a, b$ に対して，

\[ax + by = \gcd(a, b)\]

を満たす整数の組 $(x, y)$ を「ユークリッドの互除法」を応用して求める． ただし，解が複数存在する場合は $\lvert x \rvert + \lvert y \rvert$ が最小となるものとする． また，さらに最小のものが複数存在する場合は $x \leq y$ であるものとする．

この解を $(x_0, y_0)$ とすると，他の解は

\[\left( x_0 + k \cdot \frac{b}{\gcd(a,b)}, \ y_0 - k \cdot \frac{a}{\gcd(a,b)} \right)\]

から求められる（ただし，$k$ は整数）．

アルゴリズムの計算量は $\mathcal{O}(\log(\min(a,b)))$ となる．

参考文献

1. H.H. シルヴァーマン. “第6章 一次方程式と最大公約数”. はじめての数論. 鈴木治郎訳. 原著第4版, 丸善出版, 2022, p.36-43.
2. “ユークリッドの互除法”. Wikipedia. https://ja.wikipedia.org/wiki/ユークリッドの互除法.
3. drken. “拡張ユークリッドの互除法 〜 一次不定方程式 ax + by = c の解き方 〜”. Qiita. https://qiita.com/drken/items/b97ff231e43bce50199a.
4. “拡張ユークリッドの互除法の解の範囲”. HatenaBlog. https://satashun.hatenablog.com/entry/2019/12/30/231319.

Verified with

• verify/aoj-NTL_1_E-extgcd.test.cpp

Code

#ifndef ALGORITHM_EXTGCD_HPP
#define ALGORITHM_EXTGCD_HPP 1

/**
 * @brief 拡張ユークリッドの互除法
 * @docs docs/Math/NumberTheory/extgcd.md
 */

namespace algorithm {

// 拡張ユークリッドの互除法．
// ax+by=gcd(a,b) を満たす整数の組(x,y)を求め，gcd(a,b)を返す．O(log(min(a,b))).
template <typename Type>
Type extgcd(Type a, Type b, Type &x, Type &y) {
    if(b == 0) {
        x = 1, y = 0;
        return a;
    }
    Type &&d = extgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

}  // namespace algorithm

#endif

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



/**
 * @brief 拡張ユークリッドの互除法
 * @docs docs/Math/NumberTheory/extgcd.md
 */

namespace algorithm {

// 拡張ユークリッドの互除法．
// ax+by=gcd(a,b) を満たす整数の組(x,y)を求め，gcd(a,b)を返す．O(log(min(a,b))).
template <typename Type>
Type extgcd(Type a, Type b, Type &x, Type &y) {
    if(b == 0) {
        x = 1, y = 0;
        return a;
    }
    Type &&d = extgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

}  // namespace algorithm

Back to top page