Math/NumberTheory/ExtendedEuclid.h

• View this file on GitHub
• Last update: 2022-01-06 17:46:09+08:00

Required by

• Math/NumberTheory/ChineseRemainder.h

Verified with

• Math/tests/aizu_ntl_1_e_extended_euclid.test.cpp
• Math/tests/ntt_chemthan_any_mod_2.test.cpp

Code

// Dùng Extended Euclid để tìm nghiệm của phương trình ax + by = gcd(a, b).
// Giả sử kết quả trả về là (x0, y0), họ nghiệm của phương trình sẽ là (x_0+kb/d,y_0-ka/d) với k∈Z.
// Phương trình tổng quát ax + by = d chỉ có nghiệm khi d chia hết cho gcd(a, b).
// a x + b y = gcd(a, b)
template<typename T>
T extgcd(T a, T b, T &x, T &y) {
    T g = a; x = 1; y = 0;
    if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
    return g;
}

#line 1 "Math/NumberTheory/ExtendedEuclid.h"
// Dùng Extended Euclid để tìm nghiệm của phương trình ax + by = gcd(a, b).
// Giả sử kết quả trả về là (x0, y0), họ nghiệm của phương trình sẽ là (x_0+kb/d,y_0-ka/d) với k∈Z.
// Phương trình tổng quát ax + by = d chỉ có nghiệm khi d chia hết cho gcd(a, b).
// a x + b y = gcd(a, b)
template<typename T>
T extgcd(T a, T b, T &x, T &y) {
    T g = a; x = 1; y = 0;
    if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
    return g;
}

Back to top page