Math/NumberTheory/ChineseRemainder.h

• View this file on GitHub
• Last update: 2022-02-06 13:20:09+08:00
• Link: https://oj.vnoi.info/problem/icpc21_mt_d
• Link: https://open.kattis.com/problems/generalchineseremainder

Depends on

• Math/NumberTheory/ExtendedEuclid.h

Verified with

• Math/tests/ntt_chemthan_any_mod_2.test.cpp

Code

// Solve linear congruences equation:
// - a[i] * x = b[i] MOD m[i] (mi don't need to be co-prime)
// Tested:
// - https://open.kattis.com/problems/generalchineseremainder
// - https://oj.vnoi.info/problem/icpc21_mt_d
#include "ExtendedEuclid.h"
template<typename T>
bool linearCongruences(
        const vector<T> &a,
        const vector<T> &b,
        const vector<T> &m,
        T &x,
        T &M
) {
    int n = a.size();
    x = 0; M = 1;
    for (int i = 0; i < n; i++) {
        T a_ = a[i] * M, b_ = b[i] - a[i] * x, m_ = m[i];
        T y, t, g = extgcd<T>(a_, m_, y, t);
        if (b_ % g) return false;
        b_ /= g; m_ /= g;
        x += M * (y * b_ % m_);
        M *= m_;
    }
    x = (x + M) % M;
    return true;
}

#line 1 "Math/NumberTheory/ChineseRemainder.h"
// Solve linear congruences equation:
// - a[i] * x = b[i] MOD m[i] (mi don't need to be co-prime)
// Tested:
// - https://open.kattis.com/problems/generalchineseremainder
// - https://oj.vnoi.info/problem/icpc21_mt_d
#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;
}
#line 7 "Math/NumberTheory/ChineseRemainder.h"
template<typename T>
bool linearCongruences(
        const vector<T> &a,
        const vector<T> &b,
        const vector<T> &m,
        T &x,
        T &M
) {
    int n = a.size();
    x = 0; M = 1;
    for (int i = 0; i < n; i++) {
        T a_ = a[i] * M, b_ = b[i] - a[i] * x, m_ = m[i];
        T y, t, g = extgcd<T>(a_, m_, y, t);
        if (b_ % g) return false;
        b_ /= g; m_ /= g;
        x += M * (y * b_ % m_);
        M *= m_;
    }
    x = (x + M) % M;
    return true;
}

Back to top page