5.4 KiB
一、题目描述
给定 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
输入样例：
2
8 7
11 9
输出样例：
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
扩展中国剩余定理
本题中 并未说m_1,m_2,…,m_n之间两两互质,需要重新推导:
推导
\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;
}
```