概念

中国剩余定理（\(\texttt{Chinese Remainder Theorem}\), \(\tt CRT\)）可以求解关于 \(x\) 的线性同余方程组

\[\begin{cases} x \equiv a_1(\bmod p_1)\\ x \equiv a_2(\bmod p_2)\\ ...\\ x \equiv a_k(\bmod p_k) \end{cases} \]

其中 \(p_1, p_2, ..., p_k\) 两两互质。

思想

设 \(M = \prod\limits_{i = 1}^k p_i\)，\(m_i = \frac{M}{p_i}\)

另设 \(m_i^{-1}\) 为 \(m_i\) 在模 \(p_i\) 意义下的逆元，即 \(m_im_i^{-1} \equiv 1(\bmod p_i)\)

则方程的唯一解为 \(x = \sum\limits_{i = 1}^k a_im_im_i^{-1}\)

证明

首先证明方程解的正确性。

\[\because \forall i \neq j, m_j \equiv \frac{M}{p_j} \equiv 0(\bmod p_i)\\ \because m_jm_j^{-1} \equiv m_j \equiv 0(\bmod p_i) \textsf{且} m_im_i^{-1} \equiv 1(\bmod p_i)\\ \begin{aligned} \therefore \forall &1 \leq i \leq k,\\ x &\equiv \sum\limits_{j = 1}^k a_jm_jm_j^{-1} &(\bmod p_i)\\ &\equiv a_im_im_i^{-1} & (\bmod p_i)\\ &\equiv a_i &(\bmod p_i) \end{aligned} \]

然后证明方程解在模 \(M\) 意义下的唯一性。

考虑采用反证法。

设原方程组在模 \(M\) 意义下有两个不同的整数解 \(x, y\)，

则 \(\forall 1 \leq i \leq k\)，有 \(x \equiv (x \bmod m) \equiv y(\bmod p_i)\)

所以 \(x, y\) 在模 \(M\) 意义下是同一个解。

模板

P1495 【模板】中国剩余定理(CRT)/曹冲养猪

#include <cstdio>
using namespace std;

typedef long long ll;

const int maxn = 15;

int n;
ll mul;
ll a[maxn], p[maxn], inv[maxn], m[maxn];

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

int main()
{
	ll x, y, ans = 0;
	mul = 1;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld%lld", &p[i], &a[i]);
		mul *= p[i];
	}
	for (int i = 1; i <= n; i++)
	{
		m[i] = mul / p[i];
		exgcd(m[i], p[i], inv[i], y);
		ans = (ans + a[i] * m[i] * (inv[i] < 0 ? inv[i] + p[i] : inv[i]));
	}
	printf("%lld\n", ans % mul);
	return 0;
}