孙子定理是中国古代求解一次同余式组（见同余）的方法。是数论中一个重要定理。 又称中国余数定理。一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题， 原文如下： 有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？ 即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题， 以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。 具体的解法可以去参考以下链接 这里 还有 这里 其实就是对于一个多次同余方程的求解 可以举个例子用数学方法算一下 例五：三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。
除以3余2和除以7余2的数可以写成21n+2。
21n+2除以5余3，要求21n除以5余1。
21n除以5余1，21除以5余1，要求n除以5余1
（乘数之余等于余数之乘），则n最小取1。
所以满足“除以3余2，除以5余3，除以7余2”的最小的数是21×1+2=23。

标准解法：先从3和5、3和7、5和7的公倍数中相应地找出分别被7、5、3除均余1的较小数15、21、70 ( 注释:此步又称为求"模逆"运算,利用扩展欧几里得法并借助计算机编程可比较快速地求得.当然,对于很小的数,可以直接死算 )。即

15÷7=2……余1，
21÷5=4……余1，
70÷3=23……余1.
再用找到的三个较小数分别乘以所要求的数被7、5、3除所得的余数的积连加，
15×2+21×3+70×2=233. (将233处用i代替，用程序可以求出)
最后用和233除以3、5、7三个除数的最小公倍数.
233÷105=2……余23，
这个余数23就是合乎条件的最小数.

答案

对于这个我们有两种算法 

1 大数翻倍法

#include<algorithm>
//会用到一个很神奇滴函数，加着
#include<iostream>
using namespace std;
long long n,a[11],b[11],i,ans,c;
//用long long定义
long long zxgbs(long long a,long long b)
{
	return a*b// __gcd(a,b);
}
//求最小公倍数
int main(){
	cin>>n;
	for(i=1;i<=n;i++)
		cin>>a[i]>>b[i];
    //输入部分，不说了
	c=a[1];ans=b[1];
    //第一次建立不用循环，直接写进去
	for(i=2;i<=n;i++)
	{
		for(;ans%a[i]!=b[i];) ans+=c;
        //ans暴力往上加，加到符合这次的标准
		c=zxgbs(c,a[i]);
        //用函数把a[i]加进去，后面每次加的都要是这次的倍数
	}
	cout<<ans;
    //输出结果
	return 0;
} 

　　2.EX—gcd

#include<cstdio>
#define ll long long
ll n,a[16],m[16],Mi[16],mul=1,X;
inline int rd(){
    int io=0;char in=getchar();
    while(in<'0'||in>'9')in=getchar();
    while(in>='0'&&in<='9')io=(io<<3)+(io<<1)+(in^'0'),in=getchar();
    return io;
}
void exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){x=1;y=0;return ;}
    exgcd(b,a%b,x,y);
    int z=x;x=y,y=z-y*(a/b);
}
int main(){
    n=rd();
    for(int t=1;t<=n;++t){
        int M=rd();m[t]=M;
        mul*=M;
        a[t]=rd();
    }
    for(int t=1;t<=n;++t){
        Mi[t]=mul/m[t];
        ll x=0,y=0;
        exgcd(Mi[t],m[t],x,y);
        X+=a[t]*Mi[t]*(x<0?x+m[t]:x);
    }
    printf("%lld",X%mul);
    return 0;
}

　　这就是CRT

但是我们知道GCD后有EX—gcd 所以CRT后也有EX—CRT

EX—CRT是这么说的（两数不互质）

 

PS 这里的Ai是不互质的，所以EXcrt根本不可能用CRT去解

代码如下

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
bool flag = false;
ll a1,a2,n1,n2;
ll n;
ll as[100001];
ll ns[100001];
void exgcd(ll a,ll b,ll g,ll &x,ll &y) {
	if (b == 0) {
		g = a;
		x = 1;
		y = 0;
		return;
	}
	exgcd(b,a%b,g,y,x);
	y-=(a/b)*x;
}
void china() {
	ll d = a2 - a1;
	ll g,x,y;
	exgcd(n1,n2,g,x,y);
	if (d % g == 0) {
		x = ((x*d/g)%(n2/g)+(n2/g))%(n2/g);
		a1 = x*n1 + a1;
		n1 = (n1*n2)/g;
	} else
		flag = true;
}
ll multi(ll a,ll b,ll m)
{
	ll ret=0;
	
	while(b!=0)
	{
		if(b&1)
		{
			ret=(ret+a)%m;
		}
		a=(a*2)%m;
		b/=1;
	}
	
	return ret;
}
ll excrt() {
	a1 = as[0];
	n1 = ns[0];
	for (ll i = 1; i<n; i++) {
		a2 = as[i];
		n2 = ns[i];
		china();
		if (flag)
			return -1;
	}
	return a1;
}
int main() {
	cin>>n;
	flag = false;
	for (ll i = 0; i<n; i++)
		cin>>ns[i]>>as[i];
	cout<<1ll*excrt()<<endl;
}

　　今天终于考完颓荐生考试了，考的怎么样还要等到明天才出成绩，所以，本蒟蒻可能就要暂时离开OI的练习了，今天用了一点课余时间统计了一下我的刷题数

从1月9日开始学OI开始 到2020/06/27 我已经刷了597道题了

如果成绩不是很理想的话，可能就要暂别机房了...

近六个月的学习，很快乐很苦也很充实，今天来打个卡，庆祝一下我洛谷刷题破300（虽然水了好多红题qwq）

但愿明天成绩不错....