中国剩余定理（又名孙子定理）是数论四大定理（威尔逊定理、中国剩余定理、欧拉定理、费马小定理）之一，这里介绍中国剩余定理以及扩展后的定理内容以及在ACM中的应用。

        首先介绍中国剩余定理的内容。

【中国剩余定理】对于一次线性同余方程组：

        如果$gcd(m_i,m_j)=1,1\leq i<j\leq n$，则$x$在模$M=\displaystyle \prod_{i=1}^n m_i$意义下有唯一解。该解可以通过下面方法得到：
        规定$M_i=\displaystyle\frac {M} {m_i}$，并设$M_i^{-1}为M_i在模m_i下的乘法逆元$，那么解为：

        证明参考数论相关书目，这里略。
        关于乘法逆元可以见这篇文章。
        中国剩余定理可以帮助求一次线性同余方程组的解。但是当模数m不满足两两互素时，定理便不再适用，于是需要引入更一般化的定理。
        先给出一个一次线性同余方程组：

        化同余式为：

        记这个式子为①式，化①为同余式：

        设$d=gcd(m_1,m_2)$，由上式可得$d|(a_2-a_1)$，若否则方程组无解。下面仅讨论有解的情况。
        上式等价于：

        显然$\displaystyle\frac {m_1} {d}$与$\displaystyle\frac {m_2} {d}$互质，于是$\displaystyle\frac {m_1} {d}$在模$\displaystyle\frac {m_2} {d}$意义下存在乘法逆元，那么：

        化上式为：

        将上式代入①式：

        化为同余式：

        于是得到了一个同余式。易见上面的变形都是等价变形，故该同余式的解与原方程组相同，这样就将两个同余方程合并成一个，并且这个同余方程的解是显见的。
        反复利用这个公式，可以将n个方程化为一个同余方程。中国剩余定理可以认为是这个公式的特例，这样就得到了一般化的定理。下面用HDU 1573(X问题)来应用这个公式。

        求在小于等于N的正整数中有多少个X满足：X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2], …, X mod a[i] = b[i], … (0 < a[i] <= 10,0 < N <= 1000,000,000 , 0 < M <= 10)

        其实这个问题很裸地考察上面推导出的公式，直接应用即可。代码中用扩展欧几里得算法求逆元。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>

using namespace std;
int N, M, a[15], b[15], flag = 1;

int gcd(int x, int y) {
    if (y == 0)return x;
    return gcd(y, x % y);
}

int egcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int p = egcd(b, a % b, y, x);
    y -= a / b * x;
    return p;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        flag = 1;
        cin >> N >> M;
        for (int i = 1; i <= M; i++)cin >> a[i];//模数
        for (int i = 1; i <= M; i++)cin >> b[i];
        for (int i = 2; i <= M; i++) {//全部合并到a[1],b[1]中
            int d = gcd(a[1], a[i]), e = b[i] - b[1], x, y;
            if (e % d != 0) {//无解
                cout << 0 << endl, flag = 0;
                break;
            }
            egcd(a[1], a[i], x, y);//扩展欧几里得求逆元
            b[1] = b[1] + a[1] * e / d * x;
            a[1] = a[1] * a[i] / d;
            b[1] = (b[1] % a[1] + a[1]) % a[1];
        }
        if (flag) {
            if (b[1] > 0)cout << (N >= b[1] ? (N - b[1]) / a[1] + 1 : 0) << endl;
            else if (b[1] == 0)cout << N / a[1] << endl;
        }
    }
    return 0;
}

        这里有一个常用的技巧：C++中的%运算符得到的并不一定是数学上的模（要求非负），可以用表达式$(a\%p+p)\%p$将其化为数学上非负的模。