[数论]中国剩余定理

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

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

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

$$begin{cases} xequiv a_1(mod m_1)\ xequiv a_2(mod m_2)\ cdots \ xequiv a_n(mod m_n) end{cases}$$

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

$$xequiv sum_{i=1}^n a_iM_iM_i^{-1}(mod M)$$

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

$$begin{cases} xequiv a_1(mod m_1)\ xequiv a_2(mod m_2)end{cases}$$

        化同余式为：

$$x=a_1+k_1m_1=a_2+k_2m_2,(k_1,k_2in mathbb {Z})$$

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

$$k_1m_1equiv a_2-a_1(mod m_2)$$

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

$$k_1frac {m_1} {d}equiv frac{a_2-a_1} {d}(mod frac {m_2} {d})$$

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

$$k_1equiv frac {a_2-a_1} {d} (frac {m_1} {d})^{-1}(mod frac {m_2} {d})$$

        化上式为：

$$k_1=frac {a_2-a_1} {d} (frac {m_1} {d})^{-1}+kfrac {m_2} {d},(kin mathbb {Z})$$

        将上式代入①式：

$$x=a_1+m_1(frac {a_2-a_1} {d})(frac {m_1} {d})^{-1}+kfrac {m_1m_2} {d}$$

        化为同余式：

$$xequiv a_1+m_1(frac {a_2-a_1} {d})(frac {m_1} {d})^{-1}(mod frac {m_1m_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

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

int (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$将其化为数学上非负的模。