(EX)中国剩余定理

中国剩余定理

问题引入：

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？《孙子算经》

就是计算一个数\(x\)满足\(\begin{cases} x≡2(MOD\ 3) \\ x≡3(MOD\ 5) \\ x≡2(MOD\ 7) \end{cases}\)

中国剩余定理：

首先对于同余方程，以下等式显然成立：

\[(\sum a_i)\%p ≡ \sum (a_i\%p)\ (MOD\ p)①
\]

接下来我们构造三个数\(a,b,c\)满足以下条件：

\[\left[ \begin{array}{ccc}
a\%3=2 & a\%5=0 & a\%7=0 \\
b\%3=0 & b\%5=3 & b\%7=0 \\
c\%3=0 & c\%5=0 & c\%7=2
\end{array} \right]\]

可以发现根据等式\(①\)，\(a+b+c\)即为所求\(x\)的一个解

现在考虑如何构造\(a,b,c\)三个数

首先\(a\)是\(5\)的倍数也是\(7\)的倍数，所以\(a\)是\(35\)的倍数，同理，\(b\)是\(21\)的倍数，\(c\)是\(15\)的倍数

所以令

\[\begin{cases}
a = 35\cdot k_a \\
b = 21\cdot k_b \\
c = 15\cdot k_c
\end{cases}\]

则

\[\begin{cases}
35\cdot k_a ≡ 2\ (MOD\ 3)\\
21\cdot k_b ≡ 3\ (MOD\ 5)\\
15\cdot k_c ≡ 2\ (MOD\ 7)
\end{cases}\]

设\(35\)在模\(3\)意义下的逆元为\(inv_a\)，\(21\)在模\(5\)意义下的逆元为\(inv_b\)，\(15\)在模\(7\)下的逆元为\(inv_c\)

\(inv_a = 2，inv_b = 1，inv_c = 1\)

则

\[\begin{cases}
k_a = 2\cdot inv_a = 4\\
k_b = 3\cdot inv_b = 3\\
k_c = 2\cdot inv_c = 2
\end{cases}
\]

所以：

\[\begin{cases}
a = 140\\
b = 63\\
c = 30
\end{cases}
\]

所以得到\(x\)的一个解\(x=a+b+c=233\)

如果要求得所有\(x\)中最小的非负整数解，只要用\(x\)对\(lcm(3,5,7)\)取模即可

所以最后得到的最小的\(x = 233\%(3\cdot 5\cdot 7)=23\)

推广到一般情况下：

\[求出最小的x满足：
\begin{cases}
x ≡ r_1\ (MOD\ p_1)\\
x ≡ r_2\ (MOD\ p_2)\\
\quad \quad \quad \vdots\\
x ≡ r_m\ (MOD\ p_m)\\
\end{cases}，其中\forall gcd(p_i,p_j)=1\]

\[记 P = \prod_{i=1}^{m}p_i，inv_i为\frac{P}{p_i}在模p_i意义下的逆元
\]

\[在模P意义下得到x的唯一解：x = (\sum_{i=1}^{m}r_i\cdot \frac{P}{p_i}\cdot inv_i)\%P
\]

例题：

HDU1370 Biorhythms

view code

//#pragma GCC optimize("O3")

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

typedef long long int LL;

const LL p[3] = {23,28,33};

void exgcd(LL a, LL b, LL &x, LL &y){

    if(!b){ x = 1; y = 0; return; }

    exgcd(b,a%b,y,x);

    y -= a / b * x;

}

void solve(LL a[], LL d, int kase){

    for(int i = 0; i < 3; i++) a[i] %= p[i];

    LL P = p[0] * p[1] * p[2], sum = 0;

    for(int i = 0; i < 3; i++){

        LL inv, y;

        exgcd(P/p[i],p[i],inv,y);

        sum = (sum + P/p[i]*inv%P*a[i]%P) % P;

    }

    LL day = (sum%P+P)%P - d; if(day<=0) day += P;

    printf("Case %d: the next triple peak occurs in %I64d days.\n",kase,day);

}

int main(){

    int tt; ____();

    for(cin >> tt; tt; tt--){

        LL a[3], d;

        int kase = 1;

        while(cin >> a[0] >> a[1] >> a[2] >> d and (a[0]+a[1]+a[2]+d+4)) solve(a,d,kase++);

    }

    return 0;

}

扩展中国剩余定理

\[求解线性同余方程组：
\begin{cases}
x ≡ r_1\ (MOD\ p_1) \\
x ≡ r_2\ (MOD\ p_2) \\
\quad \quad \quad \vdots \\
x ≡ r_m\ (MOD\ p_m)
\end{cases}
，\exists gcd(p_i,p_j)\ne 1
\]

首先考虑两个同余方程：

\[\begin{cases}
x ≡ r_1\ (MOD\ p_1) \\
x ≡ r_2\ (MOD\ p_2)
\end{cases}
，gcd(p_1,p_2)\ne 1
\]

可以得到：

\[p_1 \cdot k_1 + r_1 = p_2 \cdot k_2 + r_2\]

\[\Downarrow
\]

\[p_1 \cdot k_1 - p_2 \cdot k_2 = r_2 - r_1
\]

根据裴蜀定理，\((r_2-r_1) \% gcd(p_1,p_2)\ne 0\)的情况下是无解的

在\((r_2-r_1) \% gcd(p_1,p_2) = 0\)的情况下，可以通过扩展欧几里得求得\(k_1\)和\(k_2\)

然后就可以得到：

\[x ≡ p_1\cdot k_1 + r_1\ (MOD\ lcm(p_1,p_2))
\]

\[OR
\]

\[x ≡ p_2\cdot k_2 + r_2\ (MOD\ lcm(p_1,p_2))
\]

对于多个方程的情况下，两两合并即可

例题：

洛谷P4777