This documentation is automatically generated by online-judge-tools/verification-helper
// 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;
}