math/external_gcd.hpp

• View this file on GitHub
• Last update: 2024-06-20 15:39:33+09:00
• Include: #include "math/external_gcd.hpp"
• Link: View error logs on GitHub Actions

Required by

• Fiducciaのアルゴリズム (きたまさ法?) (formal-power-series/fiduccia.hpp)
• Formal Power Series (形式的べき級数) (formal-power-series/formal-power-series.hpp)
• mod 998244353でのFPS(Formal Power Series, 形式的べき級数) (formal-power-series/fps998.hpp)
• formal-power-series/naive-fps.hpp
• sparse-fps (formal-power-series/sparse-fps.hpp)
• modint (math/modint.hpp)
• test/verify/fps/yosupo-inv-of-formal-power-series-naive-test.cpp

Verified with

• test/unittest/unittest-multiple-divisor-moebius-transform.test.cpp
• test/verify/atcoder-tdpc-s.test.cpp
• test/verify/convolution/yosupo-and-convolution.test.cpp
• test/verify/convolution/yosupo-gcd-convolution.test.cpp
• test/verify/convolution/yosupo-lcm-convolution.test.cpp
• test/verify/convolution/yosupo-normal-convolution.test.cpp
• test/verify/fps/yosupo-division-of-polynomials.test.cpp
• test/verify/fps/yosupo-exp-of-formal-power-series.test.cpp
• test/verify/fps/yosupo-inv-of-formal-power-series-fast2.test.cpp
• test/verify/fps/yosupo-inv-of-formal-power-series-sparse.test.cpp
• test/verify/fps/yosupo-kth-term-of-linearly-recurrent-sequence.test.cpp
• test/verify/fps/yosupo-log-of-formal-power-series.test.cpp
• test/verify/fps/yosupo-pow-of-formal-power-series.test.cpp
• test/verify/math/matrix/yosupo-inverse-of-matrix.test.cpp
• test/verify/math/matrix/yosupo-linear-equation.test.cpp
• test/verify/math/matrix/yosupo-matrix-product.test.cpp
• test/verify/math/matrix/yosupo-pow-of-matrix.test.cpp
• test/verify/math/matrix/yosupo-rank-of-matrix.test.cpp
• test/verify/yosupo-deque-operate-all-composite.test.cpp
• test/verify/yosupo-queue-operate-all-composite.test.cpp
• test/verify/yosupo-vertex-set-path-composite.test.cpp
• test/verify/yuki-372-itsautomatic.test.cpp

Code

#ifndef HARUILIB_MATH_EXTERNAL_GCD_HPP
#define HARUILIB_MATH_EXTERNAL_GCD_HPP

#include <tuple>

// g,x,y
template<typename T>
constexpr std::tuple<T, T, T> extendedGCD(T a, T b) {
    T x0 = 1, y0 = 0, x1 = 0, y1 = 1;
    while (b != 0) {
        T q = a / b;
        T r = a % b;
        a = b;
        b = r;
        
        T xTemp = x0 - q * x1;
        x0 = x1;
        x1 = xTemp;
        
        T yTemp = y0 - q * y1;
        y0 = y1;
        y1 = yTemp;
    }
    return {a, x0, y0};
}
#endif // HARUILIB_MATH_EXTERNAL_GCD_HPP

#line 1 "math/external_gcd.hpp"



#include <tuple>

// g,x,y
template<typename T>
constexpr std::tuple<T, T, T> extendedGCD(T a, T b) {
    T x0 = 1, y0 = 0, x1 = 0, y1 = 1;
    while (b != 0) {
        T q = a / b;
        T r = a % b;
        a = b;
        b = r;
        
        T xTemp = x0 - q * x1;
        x0 = x1;
        x1 = xTemp;
        
        T yTemp = y0 - q * y1;
        y0 = y1;
        y1 = yTemp;
    }
    return {a, x0, y0};
}

Back to top page