起源 在《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二（除以3余2），五五数之剩三（除以5余3），七七数之剩二（除以7余2），问物几何？”这个问题称为“孙子问题”，该问题的一般解法国际上称为“中国剩余定理”。
解法：1、找出三个数，从3和5的公倍数中找出取余7等于1的数（即15），从3和7的公倍数中找出取余5等于1的数（即21）从5和7的公倍数中找出取余3等于1的数（即70）。
2、用15乘以2（即x除以7的余数），用21乘以3（即x除以5的余数），用70乘以2（即x除以3的余数），将这三个数加起来，得到30+63+140=233。
3、求3，5，7这三个数的最小公倍数，即105。用233除以105，求出余数为23，23就是符合这个要求的最小解。
解释
首先引入一个公式，即 若a%b=c，则有(a+k*c)%b=c(其中k为整数）。因此设三个数n1,n2,n3，这三个数满足n1%3=2, n2%5=3，n3%7=2。如果要让(n1+n2)%3=2，则需要上面的公式，即n2是3的倍数就成立，同理，要让（n1+n2+n3)%3=2，即让n2,n3都为3的倍数，因此要满足上面的三个公式，就有
1、n1需要是5和7的倍数，n1%3=2。
2、n2需要是3和7的倍数，n2%5=3。
3、n3需要是3和5的倍数，n3%7=2。
要得到最终解，就是（n1+n2+n3)，要得到最小解，由第一个公式得即（n1+n2+n3)%105。
代码解决
首先解决求n1，n2，n3的过程，要求n1，应该先在5和7的公倍数中，找到n1%3=1的数，再用这个数乘2，即求5和7的公倍数在取余3时的逆元，在用这个逆元乘2。
求逆元的方法
//拓展欧几里得 ll exgcd(ll a,ll b,ll &x,ll &y) { if(b==0){ x=1; y=0; return a; } ll ret=exgcd(b,a%b,y,x); y-=a/b*x; return ret; } //费马小定理 ll qkpow(ll a,ll p,ll mod) { ll t=1,tt=a%mod; while(p) { if(p&1)t=t*tt%mod; tt=tt*tt%mod; p>>=1; } return t; } ll getInv(ll a,ll mod) { return qkpow(a,mod-2,mod); }
代码实现
ll china(ll a[],ll b[],int n) //a[]为除数，b[]为余数，n为个数 { ll M=1,y,x=0; for(int i=0;i<n;i++){ M*=a[i]; } for(int i=0;i<n;i++){ ll w=M/a[i]; ll tx=0; ll t=exgcd(w,a[i],tx,y); x=(x+w*(b[i]/t)*x)%M; } return (x+M)%M; }
