中国剩余定理

中国剩余定理断言，对于同余方程组 \(x \equiv a_i \pmod{m_i} \ (i = 1...n)\)

若 \(m_i\) 两两互质，则 \(x\) 在 \(\pmod{M}\) 下有唯一解。这里 \(M = m_1 m_2 ...m_n\)

中国剩余定理同时也给出了构造解的方法：

令 \(M = m_1 m_2 ...m_n ,M_i = \frac {M}{m_i}\)

显然 \((M_i ,m_i ) = 1\)，所以 \(M_i\) 关于模 \(m_i\) 的逆元存在。把这个逆元设为 \(t_i\)

于是有：$M_i t_i \equiv 1 \ \pmod{m_i} $ , \(M_i t_i \equiv 0 \ \pmod{m_j} \ (j \not= i)\)

进一步：\(a_i M_i t_i \equiv a_i \ \pmod{m_i} ,a_i M_i t_i \equiv 0 \ \pmod{m_j} \ (j \not= i)\)

因此解为 \(x \equiv a_1 M_1 t_1 + a_2 M_2 t_2 + ... + a_n M_n t_n \ \pmod{M}\)

code

int inv(int a, int b) {
	int x, y;
	exgcd(a, b, x, y);
	return x;
}
int CRT(const int a[], const int m[], n) {
	int M = 1, ret = 0;
	for (int i = 1; i <= n; i++) M *= m[i];
	for (int i = 1; i <= n; i++) {
		int Mi = M / m[i], ti = inv(Mi, m[i]);
		ret = (ret + a[i] * Mi * ti) % mod;
	}
	return ret;
} 
           

原生例题

今有物不知其数, 三三数之剩二, 五五数之剩三, 七七数之剩二, 问物几何?

\(x \equiv 2 \ \pmod 3 ...... (1)\)

\(x \equiv 3 \ \pmod 5 ...... (2)\)

\(x \equiv 2 \ \pmod 7 ...... (3)\)

解

\(a_i = {2,3,2},m_i = {3,5,7},M = 3 ∗ 5 ∗ 7 = 105\)

\(M_i = \{\frac{105}{3},\frac{105}{5},\frac{105}{7} \} = \{35,21,15 \}\)

\(m_i = \{ inv(35,3),inv(21,5),inv(15,7) \} = \{2,1,1 \}\)

\(x \equiv 2 \times (35 \times 2) + 3 \times (21 \times 1) + 2 \times (15 \times 1)\)

\(x \equiv 233 \equiv 23 \ \pmod{105}\)