中国剩余定理
输入a,m 第i个方程表示为x ≡ ai(mod mi),求x。
两两互质:
const int maxn = 20; ll a[maxn], m[maxn], n; ll CRT(ll a[], ll m[], int n) { ll M = 1; for (int i = 0; i < n; i++) M *= m[i]; ll ret = 0; for (int i = 0; i < n; i++) { ll x, y; ll tm = M / m[i]; extend_gcd(tm, m[i], x, y); ret = (ret + tm * x * a[i]) % M; } return (ret + M) % M; }
POJ:2891 两两不互质
当两两不互质时,不能够用上述方法求,但可以通过将两个方程合并成一个方程的形式。
const int maxn = 1000; ll a[maxn], m[maxn], n; ll CRT(ll a[], ll m[], int n) { if (n == 1) { if (m[0] > a[0]) return a[0]; else return -1; } ll x, y, d; for (int i = 1; i < n; i++) { if (m[i] <= a[i]) return -1; d = extend_gcd(m[0], m[i], x, y); if ((a[i] - a[0]) % d != 0) return -1; ll t = m[i] / d; x = ((a[i] - a[0]) / d * x % t + t) % t; a[0] = x * m[0] + a[0]; m[0] = m[0] * m[i] / d; a[0] = (a[0] % m[0] + m[0]) % m[0]; } return a[0]; }