library/math/ExtraGCD.hpp

• View this file on GitHub
• Last update: 2025-11-24 18:49:07+09:00
• Include: #include "library/math/ExtraGCD.hpp"

Depends on

• build/pch/stdc++.hpp

Required by

• library/formalpowerseries/Sqrt.hpp
• library/math/ModularSqrt.hpp
• library/mod/Modint.hpp

Verified with

• test/AOJ/2971.test.cpp
• test/AOJ/NTL_1_E.test.cpp
• test/library-checker/Convolution/BitwiseAndConvolution.test.cpp
• test/library-checker/Convolution/BitwiseXorConvolution.test.cpp
• test/library-checker/Convolution/SubsetConvolution.test.cpp
• test/library-checker/DataStructure/PointSetRangeComposite.test.cpp
• test/library-checker/DataStructure/QueueOperateAllComposite.test.cpp
• test/library-checker/DataStructure/RangeAffineRangeSum.test.cpp
• test/library-checker/Matrix/Det.test.cpp
• test/library-checker/Matrix/Inverse.test.cpp
• test/library-checker/Matrix/Product.test.cpp
• test/library-checker/New/NumberOfSubsequence.test.cpp
• test/library-checker/Polynomial/Convolution.test.cpp
• test/library-checker/Tree/vertex_set_path_composite.test.cpp
• test/yukicoder/117.test.cpp
• test/yukicoder/1502.test.cpp
• test/yukicoder/650.test.cpp

Code

#pragma once
using ll = long long;
std::pair<ll, ll> ext_gcd(ll a, ll b) {
    if (b == 0)
        return {1, 0};
    auto [X, Y] = ext_gcd(b, a % b);
    // bX + (a%b)Y = gcd(a,b)
    // a%b = a - b(a/b)
    // ∴ aY + b(X-(a/b)Y) = gcd(a,b)
    ll x = Y, y = X - (a / b) * Y;
    return {x, y};
}

#line 2 "library/math/ExtraGCD.hpp"
using ll = long long;
std::pair<ll, ll> ext_gcd(ll a, ll b) {
    if (b == 0)
        return {1, 0};
    auto [X, Y] = ext_gcd(b, a % b);
    // bX + (a%b)Y = gcd(a,b)
    // a%b = a - b(a/b)
    // ∴ aY + b(X-(a/b)Y) = gcd(a,b)
    ll x = Y, y = X - (a / b) * Y;
    return {x, y};
}

Back to top page