拡張Euclidの互除法
(library/number/ext_gcd.hpp)

• View this file on GitHub
• Last update: 2026-01-20 19:53:58+09:00
• Include: #include "library/number/ext_gcd.hpp"

拡張Euclidの互除法

できること

• 最大公約数 $d = gcd(a, b)$ を求める
• 通常のユークリッドの互除法の過程で、 $(ax+by=d)$ を満たす整数 $(x, y)$ （ベズーの等式）を同時に求める
• 整数解は複数考えられるが、 $\vert x \vert + \vert y \vert$ が最小のものが格納される
• $1 \le a, b$ であること

計算量

$O(\log \min(a, b))$

使い方

int a, b, x, y;
cin >> a >> b;
ext_gcd(a, b, x, y);

Verified with

• 拡張Euclidの互除法のテスト (tests/number.ext_gcd.test.cpp)

Code

#pragma once
template <typename T> T ext_gcd(T a, T b, T &x, T &y) {
    T d = a;
    if (b != 0ll) {
        d = ext_gcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1ll;
        y = 0ll;
    }
    return d;
}

#line 2 "library/number/ext_gcd.hpp"
template <typename T> T ext_gcd(T a, T b, T &x, T &y) {
    T d = a;
    if (b != 0ll) {
        d = ext_gcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1ll;
        y = 0ll;
    }
    return d;
}

Back to top page