math/extgcd.cpp

• View this file on GitHub
• Last update: 2020-04-26 17:42:59+09:00

Required by

• math/CRT.cpp

Verified with

• test/yuki1358.test.cpp

Code

template<typename T>
T extgcd(T a, T b, T &x ,T &y){
    for (T u = y = 1, v = x = 0; a; ) {
        ll q = b/a;
        swap(x -= q*u, u);
        swap(y -= q*v, v);
        swap(b -= q*a, a);
    }
    return b;
}
 

#line 1 "math/extgcd.cpp"
template<typename T>
T extgcd(T a, T b, T &x ,T &y){
    for (T u = y = 1, v = x = 0; a; ) {
        ll q = b/a;
        swap(x -= q*u, u);
        swap(y -= q*v, v);
        swap(b -= q*a, a);
    }
    return b;
}
 

Back to top page