ext_ecd
(Math/ext_gcd.hpp)

• View this file on GitHub
• Last update: 2024-08-27 18:05:12+09:00
• Include: #include "Math/ext_gcd.hpp"

Verified with

• verify/extgcd.test.cpp

Code

ll extgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    ll d = extgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

ll modinv(ll a, ll MOD) {
    ll x, y;
    extgcd(a, MOD, x, y);
    return (x % MOD + MOD) % MOD;
}

/*
@brief ext_ecd
*/

#line 1 "Math/ext_gcd.hpp"
ll extgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    ll d = extgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

ll modinv(ll a, ll MOD) {
    ll x, y;
    extgcd(a, MOD, x, y);
    return (x % MOD + MOD) % MOD;
}

/*
@brief ext_ecd
*/

Back to top page