python/TangDou/AcWing/CRT/204.md

##[$AcWing$ $204$. 表达整数的奇怪方式](https://www.acwing.com/problem/content/description/206/)

### 一、题目描述
给定 $2n$ 个整数 $a_1,a_2,…,a_n$ 和 $m_1,m_2,…,m_n$，**求一个最小的非负整数** $x$，满足 $∀i∈[1,n],x≡m_i(mod\ a_i)$。

**输入格式**
第 $1$ 行包含整数 $n$。

第 $2…n+1$ 行：每 $i+1$ 行包含两个整数 $a_i$ 和 $m_i$，数之间用空格隔开。

**输出格式**
输出最小非负整数 $x$，如果 $x$ 不存在，则输出 $−1$。
如果存在 $x$，则数据保证 $x$ 一定在 $64$ 位整数范围内。

**数据范围**
$1≤a_i≤2^{31}−1,0≤m_i<a_i$

$1≤n≤25$

**输入样例：**
```cpp {.line-numbers}
2
8 7
11 9
```

**输出样例：**
```cpp {.line-numbers}
31
```

### 二、解题思路
####  中国剩余定理

**作用:求$n$组线性同余方程的通解**

**使用前提**:对于$∀i∈[1,n],x≡m_i(mod\ a_i)$,其中若$m_1,m_2,…,m_n$ **两两互质**,则可以使用 **中国剩余定理** 来求解$x$。

形式: $$ \large \left\{\begin{matrix}
x \equiv a_1 (mod \ m_1) & \\ 
x \equiv a_2 (mod \ m_2) & \\
. & \\
. & \\
. & \\
x \equiv a_n (mod \ m_n) & \\
\end{matrix}\right.$$

**公式**

$$\large x=\begin{pmatrix}
\displaystyle \sum_{i=1}^n a_it_iM_i \end{pmatrix}mod\ M
$$

其中$t_i$是$M_i$的逆元,$M_i=M/m_i$(除了$m_i$以外的乘积)
$\large M=m_1*m_2*m_3*...*m_n$

#### 扩展中国剩余定理
本题中<font color='red' size=4><b> 并未说$m_1,m_2,…,m_n$之间两两互质</b></font>,需要重新推导:

**推导**

$$ \large  \left\{\begin{matrix}
x \equiv m_1 (mod \ a_1) & ① \\ 
x \equiv m_2 (mod \ a_2) & ② \\
. & \\
. & \\
. & \\
x \equiv m_n (mod \ a_n) & \\
\end{matrix}\right.$$

先计算两个线性同余方程组的解,之后依此类推
① 可以写成 $x=k_1∗a_1+m_1$③
② 可以写成 $x=k_2∗a_2+m_2$④

③=④ $\Rightarrow$  $k_1∗a_1+m_1=k_2∗a_2+m_2$ $\Rightarrow$  $k_1∗a_1−k_2∗a_2=m_2−m_1$⑤

根据 **裴蜀定理**,当$m_2−m_1$为$gcd(a_1,−a_2)$的倍数时,方程⑤有无穷组整数解

而$k_1∗a_1−k_2∗a_2=gcd(a_1,−a_2)=d$可以用拓展欧几里得算法来解,即$exgcd(a_1,−a_2,k_1,k_2)$

#### $Q$:$k_1∗a_1−k_2∗a_2=gcd(a_1,−a_2)=d$中的$k_1$和$k_2$通解公式是什么?

**结论**

$$
\large \left\{\begin{matrix}
k_1=k_1+k*\frac{a_2}{d} & \\ 
k_2=k_2+k*\frac{a_1}{d} & 
\end{matrix}\right.
$$

> **解释**：如果我们知道一组特解$(k_1,k_2)$,那么，可以通过任意整数倍$k$的缩放,使得$k_1$缩放$k*\frac{a_2}{d}$倍，$k_2$缩放$k*\frac{a_1}{d}$倍，得到的新$k_1,k_2$依然是方程的解。

**证明:**
设$k_1$的通解为$s_1$,$k_2$的通解为$s_2$,$k_1$的特解为$k_1$,$k_2$的特解为$k_2$
> **解释**：这么写方便些，不想再写什么$k_1',k_2'$了，太麻烦~

则：
$$
\large \left\{\begin{matrix}
a_1∗s_1−a_2∗s_2=d & \\ 
a_1∗k_1−a_2∗k_2=d & 
\end{matrix}\right.
$$

$$↓方程组同时除d$$

$$
\large \left\{\begin{matrix}
\frac{a_1}{d}*s_1-\frac{a_2}{d}*s_2=1 & ⑥\\ 
\frac{a_1}{d}*k_1-\frac{a_2}{d}*k_2=1 & 
\end{matrix}\right.
$$

$$↓相减下$$

$$\frac{a_1}{d}*(s_1-k_1)-\frac{a_2}{d}*(s_2-k_2)=0$$

$$其中\frac{a_1}{d}与\frac{a_2}{d}互质 −>s_1-k_1必然是\frac{a_2}{d}的倍数$$

$$\therefore s_1-k_1=k*\frac{a_2}{d} -> k_1=k_1+k*\frac{a_2}{d}(因为s_1必然也是k_1的整数倍)$$

$$同理得 k_2=k_2+k*\frac{a_1}{d}$$

>**傻瓜问题**$：\frac{a_1}{d}与\frac{a_2}{d}$为什么互质?
**答**：在方程组⑥中根据裴蜀定理的推论($a,b$互质的充要条件是存在整数$x,y$使$ax+by=1$)从而得出它两互质.

到此证明完毕,回归正题,求解本题。

将$k_1$通解代入③得
$$x=k_1∗a_1+m_1 -> x=(k_1+k*\frac{a_2}{d})∗a_1+m_1 ->$$

$$x=k*\overbrace{\frac{a_2}{d}*a_1}^{更新后的a1}+\underbrace{k_1*a_1+m_1}_{更新后的m_1}$$

> **令$a_1=\frac{a_2}{d}*a_1$,$m_1=k_1*a_1+m_1$,就和原来的方程一个样子，但化简掉了一个方程，问题变得简单些，只要不断的合并，最终就可以得到答案**


依此迭代,经过$n−1$次后可以将$n$个线性同余方程合并为一个方程,求最小解,只需最后$(m_1\%a_1+a_1)\%a_1)$即可

### 三、实现代码
```cpp {.line-numbers}
#include <iostream>

using namespace std;
typedef long long LL;

LL exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

LL n, a1, m1, a2, m2, k1, k2;
int main() {
    cin >> n;
    cin >> a1 >> m1; // 读入第一个方程
    n--;             // 共n-1个方程
    while (n--) {
        cin >> a2 >> m2;
        // 开始合并
        // a1*k1+(-a2)*k2=m2-m1

        // ① 求a1*k1+(-a2)*k2=gcd(a1,-a2)的解,视k1=x,k2=y
        LL d = exgcd(a1, -a2, k1, k2);
        if ((m2 - m1) % d) { // 如果不是0，则无解
            cout << -1;
            exit(0);
        }

        // ② 求 a1*k1+(-a2)*k2=m2-m1 的一组解,需要翻 (m2-m1)/d倍
        k1 *= (m2 - m1) / d;

        // ③ 求最小正整数解
        int t = abs(a2 / d);
        k1 = (k1 % t + t) % t;

        // ④ 更新a1和m1,准备下一轮合并
        m1 = k1 * a1 + m1;
        a1 = abs(a1 / d * a2);
    }
    // 输出,m1是一个解，不是最小整数解，需要模a1
    cout << (m1 % a1 + a1) % a1;
    return 0;
}
```