中国剩余定理
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
三人同行七十希，五树梅花廿一支，七子团圆正半月，除百零五便得知。
题目描述
给定 \(n\) 个整数 \(a_i\) 和 \(n\) 个整数 \(m_i\)，并保证 \(m_i\) 两两互质，求一个整数 \(x\)，使得
规定
规定 \(M\) 表示所有 \(m_i\) 的乘积，\(M_i\) 表示除了 \(m_i\) 之外的所有数的乘积。
即 \(M = m_1\cdot m_2\cdots m_n\)，\(M_i = \dfrac{M}{m_i}\)。
\(M_i^{-1}\) 规定为 \(M_i\) 模 \(m_i\) 的逆元。
公式
\(x = \sum_{i=1}^{n}a_i \cdot M_i \cdot M_i^{-1}\)
推导
从前两个方程进行考虑：
将其变形，得到：
由于上下式结果都是 \(x\)，还可以进一步的简化：
移项得：
上式中 \(a_1\)、\(a_2\) 和 \(m_2 - m_1\) 都是已知量，可以用扩展欧几里得算法求解 \(k_1\) 和 \(k_2\)。
如果最初的方程有解，就等价于 \(\gcd(a_1, a_2) \mid (m_2 - m_1)\)。
上述不定方程的所有解可以表示成以下形式：
那么 \(x\) 的所有解就可以写成 \(\left( k_1 + k \cdot \dfrac{a_2}{d} \right) \cdot a_1 + m\)。
其中 \(k\) 是一个不确定的数，\(d\) 是 \(a_1\) 和 \(a_2\) 的最大公约数。
进一步整理：
其中，\(\dfrac{a_1 \cdot a2}{d}\) 相当于 \(a_1\) 和 \(a_2\) 的最小公倍数。
可得：
此时，前面的 \(a_1 \cdot k_1 + m_1\) 是固定的，记为 \(x_0\)，后面的 \(lcm(a, b)\) 记为新的 \(a\)。
整理可得：
这时，回到上面，我们会发现这个式子和上面
很像，所以此时可以将两个式子合并，即
再用这个合并的方程与下面的方程继续合并，那么合并 \(n-1\) 次后就可以直接求解了。
代码
#include <iostream>
using namespace std;
#define int long long
int n;
int a1, m1; // 现有的方程
int a2, m2; // 需要合并的方程
bool flag = true; // flag 表示当前是否无解
int k1, k2, d, t;
int mod(int a, int b){
return (a % b + b) % b;
}
int exgcd(int a, int b, int &x, int &y){
if(!b){
x = 1, y = 0;
return a;
}
int d = exgcd(b, a%b, y, x);
y -= a / b * x;
return d;
}
signed main(){
cin >> n >> a1 >> m1;
for(int i=1; i<n; i++){
cin >> a2 >> m2;
// 求出系数
d = exgcd(a1, a2, k1, k2);
// 判断是否无解
if((m2 - m1) % d){
flag = false;
break;
}
k1 *= (m2 - m1) / d;
t = a2 / d;
k1 = mod(k1, t);
m1 = a1 * k1 + m1;
a1 = abs(a1 / d * a2);
}
if(flag){
cout << mod(m1, a1);
}
else{
puts("-1");
}
return 0;
}