什么是中国剩余定理呢？
当m1,m2,....mn的值两两互质的时候，求x的值。
假设 M = m1 * m2 * ... * mn
在设 Hi = M / mi （也就是除了mi之外，其他的m值的乘积）
由于m1,m2...mn两两互质， 所以Hi与mi是互质的。
那么Hi ^ (-1) 也就是 Hi 关于 mod mi 的逆元是存在的。
（使用扩展欧几里得算法进行求解这个逆元，因为当下只有Hi,与mi互质这一个条件
也就是 Hi * (Hi ^ -1) + y * mi = 1 使用扩展欧几里得算法将x求出，也就是Hi ^ -1）
则： x = a1 * H1 * ( H1 ^ -1) + a2 * H2 * (H2 ^ -1) + ... + ak * Hk * (Hk ^ -1). （这个就是中国剩余定理的一个通用公式，但是应用的前提条件是,m1,m2,m3...两两互质。）
以第一个方程 mod m1为例：
H1 * H ^( -1) mod m1 == 1 , 而其他的H2,H3....中都包含了m1,所以mod m1为0.
所以 x = a1 * a mod m1 . 成立。
那么问题来了：
如果m1,m2,m3...不两两互质呢。那就要用到中国剩余定理的思想，将两两方程不断合并，最后就变为了一个方程了。
还是这些方程，但是现在没有m1,m2...两两互质。该怎么办呢？
先取出前面两个方程出来。并换一种表现形式
x == k1 * m1 + a1
x == k2 * m2 + a2
那么也就是说明了
k1 * m1 + a1 == k2 * m2 + a2
--->k1 * m1 - k2 * m2 == a2 - a1
这就可以用扩展欧几里得的方式求解出一组k1,k2出来。
但是要存在有解 则 (a2 - a1) 能够整除 gcd(m1,m2);
所以真正的k1就是 k1 =k1 * (a2 - a1) / gcd(m1,m2);
而k1的通解是, k1 + k * (m2 / gcd(m1,m2));
则将k1的通解带入到方程中，就可以得到一个新的关于x的方程
x == ( k1 + k * (m2 / gcd(m1,m2)) ) * m1 + a1;
x == k1 * m1 + a1 + k * m1 * m2 / gcd(m1,m2);
x == k1 * m1 + a1 + k * lcm【m1,m2】 (lcm【m1,m2】为m1,m2的最小公倍数)
而k1 * m1 + a1 就是 新的 a1(而这个k1 * m1 + a1不就是我们每次以第一个公式作为合并基准的公式嘛) , 而 lcm【m1,m2】就是新的m1
而这个x 就是前两个方程合并 后 得到的一个新的方程。
同样，新的方程 和 第三个方程合并又可以将两个方程变为一个方程，以此类推，直到最后只剩下一个方程。
这个m1，m2,a1，k1已经在合并过程中不断发生了变化。
x == k1 * m1 + a1 + k * lcm【m1,m2】
得到的最后一个这个公式的m1和a1
实际上就是 x mod m1 == a1的含义了。
而我们要求出这个最后一个公式的其中一个满足条件的x.
所以取 x = ( a1 % m1 + m1) % m1即可。
题目链接：https://www.acwing.com/problem/content/206/
题目：
给定 2n个整数 a1,a2,…,an 和 m1,m2,…,mn，求一个最小的非负整数 x，满足 ∀i∈[1,n],x≡mi(mod ai)。
输入格式
第 1 行包含整数 n。
第 2…n+1 行：每 i+1 行包含两个整数 ai和 mi，数之间用空格隔开。
输出格式
输出最小非负整数 x，如果 x不存在，则输出 −1。
如果存在 x，则数据保证 x 一定在 64 位整数范围内。数据范围
1≤ai≤2e31 - 1,
0≤mi<ai
1≤n≤25输入样例：
2 8 7 11 9输出样例：
31
分析：
按照上面m1,m2,m3...不一定互质的分析来就可以了。
但是要注意，此题是
不要和上面的m和a混淆了。
最后此题会变为：
x == k1 * a1 + m1 + k * lcm[a1,a2]
新的m1 为 k1 * a1 + m1
新的a1为 lcm[a1.a2];
代码实现：
# include <iostream>
using namespace std;
int n;
long long exgcd(long long a ,long long b , long long & x , long long & y)
{
if(!b)
{
x = 1 , y = 0;
return a;
}
else
{
int t = exgcd(b,a % b , y , x);
y -= a / b * x;
return t;
}
}
int main()
{
scanf("%d",&n);
bool flag = true;
long long a1,m1,a2,m2;
scanf("%lld %lld",&a1,&m1); // 先存入第一个方程，我们的合并是通过两个两个不断和并为1个最后化为一个方程
for(int i = 2 ; i <= n ; i++)
{
scanf("%lld %lld",&a2,&m2);
long long k1,k2;
long long t = exgcd(a1,a2,k1,k2);
if((m2 - m1) % t) // 无解
{
flag = false;
break;
}
else
{
k1 = (m2 - m1) / t * k1; //真正的k1,k2
k2 = (m2 - m1) / t * k2; // 而k2实际上用不到
k1 = ( k1 % (a2 / t) + a2 / t ) % (a2 / t); // 最小的正整数k1, 为了防止其爆long long,k1尽量取小
m1 = k1 * a1 + m1;
a1 = a1 / t * a2; // 新的a1为 a1,a2的最小公倍数
}
}
if(flag)
{
printf("%lld\n",(m1 % a1 + a1) % a1);
}
else
{
printf("-1\n");
}
return 0;
}