Extended Euclidean Algorithm (拡張ユークリッドの互除法) (math/extended_gcd.hpp)

• View this file on GitHub
• Last update: 2025-07-07 14:21:50+09:00
• Include: #include "math/extended_gcd.hpp"
• Link: https://qiita.com/drken/items/b97ff231e43bce50199a

Required by

• test/utility/next_combination.test.cpp

Verified with

• test/math/extended_gcd.test.cpp

Code

#pragma once

/**
 * @brief Extended Euclidean Algorithm (拡張ユークリッドの互除法)
 * @note 参考: https://qiita.com/drken/items/b97ff231e43bce50199a
 */
template <class T>
T ext_gcd(T a, T b, T& x, T& y) {
    if (b == T(0)) {
        x = T(1);
        y = T(0);

        return a;
    }

    T res = ext_gcd(b, a % b, y, x);
    y -= (a / b) * x;

    return res;
}

#line 2 "math/extended_gcd.hpp"

/**
 * @brief Extended Euclidean Algorithm (拡張ユークリッドの互除法)
 * @note 参考: https://qiita.com/drken/items/b97ff231e43bce50199a
 */
template <class T>
T ext_gcd(T a, T b, T& x, T& y) {
    if (b == T(0)) {
        x = T(1);
        y = T(0);

        return a;
    }

    T res = ext_gcd(b, a % b, y, x);
    y -= (a / b) * x;

    return res;
}

Back to top page