This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ngthanhtrung23/ACM_Notebook_new
// 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; }