给定2n个整数a1,a2,…,ana1,a2,…,an和m1,m2,…,mnm1,m2,…,mn,求一个最小的整数x，满足∀i∈[1,n],x≡mi(mod ai)∀i∈[1,n],x≡mi(mod ai)。
输入格式
第1行包含整数n。
第2..n行：每i+1行包含两个整数aiai和mimi,数之间用空格隔开。
输出格式
输出整数x，如果x不存在，则输出-1。
数据范围
1≤ai≤231−11≤ai≤231−1,
0≤mi<ai0≤mi<ai
输入样例：
2
8 7
11 9
输出样例：31
题意：求出同时满足所有式子要求的最小整数x,如果不存在输出-1
思路：首先没说m互相互质，所以这不是中国剩余定理，这是线性同余方程组问题
这里摘抄一位大佬的
中国剩余定理，又名孙子定理o(*≧▽≦)ツ
能求解什么问题呢？
问题：
一堆物品
3个3个分剩2个
5个5个分剩3个
7个7个分剩2个
问这个物品有多少个
解这题，我们需要构造一个答案
我们需要构造这个答案
5*7*inv(5*7, 3) % 3 = 1
3*7*inv(3*7, 5) % 5 = 1
3*5*inv(3*5, 7) % 7 = 1
这3个式子对不对
显然这里就要用到线性同余方程用扩欧来求解
然后两边同乘你需要的数
2 * 5*7*inv(5*7, 3) % 3 = 2
3 * 3*7*inv(3*7, 5) % 5 = 3
2 * 3*5*inv(3*5, 7) % 7 = 2
令
a = 2 * 5*7*inv(5*7, 3)
b = 3 * 3*7*inv(3*7, 5)
c = 2 * 3*5*inv(3*5, 7)
那么
a % 3 = 2
b % 5 = 3
c % 7 = 2
其实答案就是a+b+c
因为
a%5 = a%7 = 0 因为a是5的倍数，也是7的倍数
b%3 = b%7 = 0 因为b是3的倍数，也是7的倍数
c%3 = c%5 = 0 因为c是3的倍数，也是5的倍数
所以
(a + b + c) % 3 = (a % 3) + (b % 3) + (c % 3) = 2 + 0 + 0 = 2
(a + b + c) % 5 = (a % 5) + (b % 5) + (c % 5) = 0 + 3 + 0 = 3
(a + b + c) % 7 = (a % 7) + (b % 7) + (c % 7) = 0 + 0 + 2 = 2
你看你看，答案是不是a+b+c(??ω?)??，完全满足题意
但是答案，不只一个，有无穷个，每105个就是一个答案（105 = 3 * 5 * 7）
根据计算，答案等于233,233%105 = 23
如果题目问你最小的那个答案，那就是23了
结论：因为我要同时满足多个式子的要求，那么我们来一个一个来满足，当前的余数我就用其他数来拼凑
因为是其他数的乘积，那么其他数mod的话都会等于0，然后只有当前数会有余数，这样就能得出一个其他所有数mod等于0，满足当前数余数要求的数了
然后我们用这个方法给每个数都求一个这样的数，然后求和，那么就能满足所有数的要求了，当然这只限于两两互质情况
不互质的中国剩余定理 - 线性同余方程组
首先为什么要互质呢
因为如果化简成最简质因子的话，如果有相同质因子，那么有可能会mod成0，那么我们也不能借用来获取自己想要的数了
如
{
x = 2 mod 4
x = 3 mod 6
x = 4 mod 8
}
6*8%4 = 0 ,所以就不行了
这里我们要用线性同余方程组，来两两合并，最后化简成一个来得出答案
然后我们就可以得出推导式
#include<cstdio> #include<string> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<map> #include<vector> #define LL long long using namespace std; LL m[1000],r[1000]; void ex_gcd(LL a,LL b,LL &d,LL &x,LL &y) { if(b==0){ x=1;y=0;d=a;return ;} ex_gcd(b,a%b,d,y,x); y-=x*(a/b); } LL gcd(LL a,LL b) { return b==0?a:gcd(b,a%b); } LL ex_CRT(int n) { LL a,b,c,c1,c2,x,y,d,N; a=m[1]; c1=r[1]; for(int i=2;i<=n;i++){ b=m[i];c2=r[i]; c=c2-c1; ex_gcd(a,b,d,x,y); if(c%d) return -1; LL b1=b/d;//转移式 x=((c/d*x)%b1+b1)%b1;// c1=a*x+c1; a=a*b1;// } /*if(c1==0){ c1=1; for(int i=1;i<=n;i++) c1=c1*m[i]/gcd(c1,m[i]); //如果题目要求要正整数，那么加上一个所有数的最小公倍数 }*/ return c1; } int main() { int T,n,Case=0; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld%lld",&m[i],&r[i]); // LL c1=1; for(int i=1;i<=n;i++) c1=c1*m[i]/gcd(c1,m[i]); printf("%lld\n",ex_CRT(n)); return 0; }