中国剩余定理推导再理解

中国剩余定理： m1, m2, m3, ... , mk 两两互质：（限制条件） x = a1 (mod m1) x = a2 (mod m2) x = a3 (mod m3) ... x = ak (mod mk) 若令 M = m1 * m2 * m3 * ... * mk Mi = M / mi,Mi(-1) 表示 Mi 模 mi 的逆. 则有解 x = a1 * M1 * M1(-1) + a2 * M2 * M2(-1) + ... + ak * Mk * Mk(-1). 其中Mi的逆元Mi(-1)可以用 Mi * x = 1 (mod mi) 来(扩展欧几里得解线性同余方程). 证明过程如下:(以下证明过程,m 和 a 弄反了,余数是m1, m2, 模数是 a1, a2). x mod a1 = m1; x mod a2 = m2; 即： x = k1 * a1 + m1; x = k2 * a2 + m2; 则: k1 * a1 + m1 = k2 * a2 + m2; 即: k1 * a1 - k2 * a2 = m2 - m1. 有解等价于: gcd (a1, a2) | m2 - m1; exgcd求出k1, k2的值,则 x = k1 * a1 + m1 ; 有不定方程所有解: k1 + k * (a2 / d), k2 + k * (a1 / d); 所以 x 的所有解: x = (k1 + k * (a2 /d )) * a1 + m1 x = a1 * k1 + m1 + k * (a1 * a2 / d) x = (a1 * k1 + m1) + k * [a1, a2]. x = x0 + k * a.

代码实现：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;  // 2e9 的数据好像一般都用long long.

LL exgcd (LL a, LL b, LL & x, LL & y) {
	if (!b) {
		x = 1;
		y = 0;
		return a;
	}
	LL d = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

int main () {
	int n;
	cin >> n;

	LL a1, m1, a2, m2;
	cin >> m1 >> a1;
	LL x, k1, k2;

	bool flag = 0;
	for (int i = 2; i <= n; i ++ ) {
		
		cin >> m2 >> a2;
	
		int d = exgcd(m1, -m2, k1, k2); // m2 正负无所谓

		if ((a2 - a1) % d) {
			flag = 1;
			break;
		}

		k1 *= (a2 - a1) / d;  
		int t = m2 / d;

		k1 = (k1 % t + t) % t;   // 数据范围卡的很紧,所以k1取最小整数解.


		x = k1 * m1 + a1;
		a1 = x;
		m1 = abs(m1 / d * m2);   // m1正数、负数均可以.
	}

	if(flag) cout << "-1" << endl;
	else cout << (x % m1 + m1) % m1 << endl;  // 答案要求最小整数解.
	return 0;
}

THE END；