中国剩余定理

线性同余方程
https://en.wikipedia.org/wiki/Chinese_remainder_theorem

任何情况下，如果想知道模合数的结果，可以把合数先分解质因数成（互质的）质数的次幂，比如说 $24 = 3 \times 8$ 而不是 $24 = 3 \times 2\times 2\times 2$

对于每个质数次幂单独求解，最后用中国剩余定理合并

所以处理没有平方因子的数的难度和质数是一样的

简介

一个整数除以$3$余$2$，除以$5$余$3$，除以$7$余$2$，求这个整数。

将除以$3$得到的余数乘以$70$，将除以$5$得到的余数乘以$21$，将除以$7$得到的余数乘以$15$，全部加起来後再减去$105$或者$105$的整数倍，得到的数就是答案（除以$105$得到的余数则为最小答案）。使用以上的方法计算就得到
$$70 \times 2 + 21 \times 3 + 15 \times 2 = 233 = 2 \times 105 + 23$$

所以最小的自然数解为$23$。
注意$70, 21, 15$所满足的性质。
$70 \bmod 3 = 1, 70 \bmod 5 = 0, 70 \bmod 7 = 0$
$21 \bmod 3 = 0, 21 \bmod 5 = 1, 21 \bmod 7 = 0$
$15 \bmod 3 = 0, 15 \bmod 5 = 0, 15 \bmod 7 = 1$

中国剩余定理

$$\left\{ \begin{matrix} x \equiv r_1 \pmod {p_1} \\ x \equiv r_2 \pmod {p_2} \\ \vdots \qquad\qquad\qquad \\ x \equiv r_n \pmod {p_n} \end{matrix} \right.$$
对于每个$i$求出$m_i$使得$m_i \bmod p_j(j \neq i) = 0$并且$m_i \bmod p_i = 1$。
最终答案就是$\sum_{i} r_i m_i$。
计算$m_i$可以先通过计算$P = \prod_i p_i$，$\frac{P}{p_i}$已经满足了第一个性质，但是不满足第二个性质，再乘以$\frac{P}{p_i}$模$p_i$的逆元就可以了。

扩展欧几里得

对于任意两个方程
$$\left\{ \begin{matrix} x \equiv r_1 \pmod {p_1} \\ x \equiv r_2 \pmod {p_2} \\ \end{matrix} \right.$$
可以合并成一个$\bmod \mathrm{lcm}(p_1, p_2)$的方程。
具体来说设$x = k_1 p_1 + r_1 = k_2 p_2 + r_2$
$$k_1 p_1 - k_2 p_2 = r_2 - r_1$$
用扩展欧几里得算法解出一组解$(k_1, k_2)$，就可以得到$x \bmod \mathrm{lcm}(p_1, p_2)$的结果了。

这个做法不要求$p_1$和$p_2$满足任何性质，是最通用的做法。

当然如果$(r_2 - r_1) \bmod \gcd(p_1, p_2) \neq 0$那么原方程无解。

实现技巧

如果取模的数字$p_i$比较小，可以不实现逆元，直接$O(\sum_{i} p_i)$暴力一遍即可。
比如Luogu P1495

#include <bits/stdc++.h>
using namespace std;
int n, a[10], b[10];
long long m = 1, z;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
		m *= a[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < a[i]; j++) {
			if (m / a[i] * j % a[i] == 1) {
				z += m / a[i] * j * b[i];
			}
/*
或者
			if (m / a[i] * j % a[i] == b[i]) {
				z += m / a[i] * j;
			}
*/
		}
	}
	cout << z % m << endl;
}

如果已知取模的数字$p_i$，可以直接暴力计算出需要的$m_i$，直接将$m_i$写入程序中。
poj 1006
答案就是$(5544p + 14421e + 1288i - d - 1) \bmod 21252 + 1$

参考题目

Luogu P1495

poj 1006

bzoj 1951
组合数对$999911659 - 1 = 2 \times 3 \times 4679 \times 35617$ 取模。

bzoj 2142
组合数对任意数取模，注意$p_i^{c_i} \leq 100000$。

参考资料

Wikipedia 中国剩余定理