中国剩余定理

常用来解一元线性同余方程组

一般从这个问题引入，某物品三三数之余二，五五数之余三，七七数之余二。问物几何？

写成方程组的形式就是求解

$$\left\{ \begin{matrix} x\equiv\ 2\ mod\ 3 \\ x\equiv\ 3\ mod\ 5 \\ x\equiv\ 2\ mod\ 7 \end{matrix} \right.$$

首先，若$x_0$为原方程的一个解，那么$x_0+3*5*7*k，k\in 整数$，也是一个解

解上述方程组其实首先需要解以下3个方程，这里有点线性代数的意思。

$$\left\{ \begin{matrix} x\equiv\ 1\ mod\ 3 \\ x\equiv\ 0\ mod\ 5 \\ x\equiv\ 0\ mod\ 7 \end{matrix} \right.$$

$$\left\{ \begin{matrix} x\equiv\ 0\ mod\ 3 \\ x\equiv\ 1\ mod\ 5 \\ x\equiv\ 0\ mod\ 7 \end{matrix} \right.$$

$$\left\{ \begin{matrix} x\equiv\ 0\ mod\ 3 \\ x\equiv\ 0\ mod\ 5 \\ x\equiv\ 1\ mod\ 7 \end{matrix} \right.$$

记上述三组的解记为

$$\begin{bmatrix} 1\\ 0\\ 0\\ \end{bmatrix}$$

$$\begin{bmatrix} 0\\ 1\\ 0\\ \end{bmatrix}$$

$$\begin{bmatrix} 0\\ 0\\ 1\\ \end{bmatrix}$$

则原方程的解为 $2*$$\begin{bmatrix} 1\\ 0\\ 0\\ \end{bmatrix}$+$3*$$\begin{bmatrix} 0\\ 1\\ 0\\ \end{bmatrix}$+$2*$$\begin{bmatrix} 0\\ 0\\ 1\\ \end{bmatrix}$

问题的关键显然是求上述三组解。 上述三组解是这样求的，先来看第一个。

$$\left\{ \begin{matrix} x\equiv\ 1\ mod\ 3 \\ x\equiv\ 0\ mod\ 5 \\ x\equiv\ 0\ mod\ 7 \end{matrix} \right.$$

$x一定是35的倍数$，所以设$x=35*y$,那么$35y\ \equiv\ 1\ mod\ 3$,这里容易求出$y$是$2$,实际也能看出就是逆元。

求出$2$以后，$x=35*2=70$，那么第一个方程组的一个特解就出来了。

同理求出其余的两个方程组的特解分别是$x=21,x=15$。

则原方程的解为$2*70+3*21+2*15\ \equiv\ 23\ mod\ 105$ ，所以这里就求出了23.

因此从这里也能看出线性同余方程组的求解方式，方法就是。

$$\left\{ \begin{matrix} x\equiv\ b_1\ mod\ a_1 \\ x\equiv\ b_2\ mod\ a_2 \\ …… \\ x\equiv\ b_k\ mod\ a_k \\ \end{matrix} \right.$$

首先还是按照刚才的方式分出多个方程组来，求出每一个的，最后求和。

1. 首先求出$N=a_1*a_2*……*a_k$
2. 对于每一组方程我们按照上面的例题思路来求解，设$m=N/a_i$,那么紧接着我们需要求出$mx\ \equiv\ 1\ mod\ a_i$,求出这个$x以后$。
3. 那么最终这个方程组的解就是$m*x*b_i$，回想刚才不就是$35是m，x求逆元是2，b_i是2$，所以是$35*2*2$,对应上面的$2*70$.
4. 然后循环求和，并且求和的时候对$N$取余得到答案。

本题实际就是

$$\left\{ \begin{matrix} x\equiv\ p\ mod\ 23 \\ x\equiv\ e\ mod\ 28 \\ x\equiv\ i\ mod\ 33 \end{matrix} \right.$$

根据刚才我们的方法，首先计算第一个式子的时候，需要算出 $28*33$ 应该就是$924$，$924$关于$23$的逆元是$6$，所以$924*6$也就是$5544$然后乘以$p$，得到第一组的答案，类似其余的答案就是$14421*e$,$1288*i$.

最终答案就是$(5544 * p + 14421 * e + 1288 * i - d + lcm) \% lcm$ 算的是距离$d$开始以后多少，所以减去$d$，同时避免出现负数所以加$lcm$以后在取余。

$lcm=23*28*33$

如果算下来答案是$0$，记得输出$lcm$而不是输出$0$

    cin >> p >> e >> i >> d;
    lcm = 23 * 28 * 33;
    ans = (5544 * p + 14421 * e + 1288 * i - d + lcm) % lcm;
    cnt++;
    if (ans == 0)
        ans = lcm;
    cout << ans;

写题解请注意

鼓励大家写题解，但注意题解格式。

题解一定要有思路解析或代码注释，能否让别人理解你的思路

也是你的能力的检验，不要只放无意义的代码给大家复制，那就失去了做题的初心。

给代码两端加上这个会舒服一些

```cpp

你的代码

```

</span>

这个点在键盘的左上角tab上面那个键，注意切换输入法

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;//这是一个注释
    return 0;
} 

请注意严禁抄袭题解，写题解不要只放代码，需加上你的思路或代码注释。

抄袭题解一经发现直接取消成绩。

题解被删除的可能

1. 代码不符合格式规范
2. 没有思路讲解或者没有注释，
3. 无意义的题解

大家携手共同维护一个良好的编程环境，如果一经发现，多次作乱。可能会被管理员拉黑，请注意，一旦拉黑即失去登陆资格。