孙子定理是中国古代求解一次同余式组（见同余）的方法。是数论中一个重要定理。又称中国余数定理。一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：
为 
模 
的数论倒数( 
为 
模 
意义下的逆元) 
方程组 
的通解形式为 
在模
的意义下，方程组 只有一个解： 
，由于 
，所以 
这说明存在整数 
使得 
叫做 模 的数论倒数。考察乘积 
可知：
所以 
就是方程组 的一个解。另外，假设 
和 
都是方程组 的解，那么：
而 
两两互质，这说明 
整除 
. 所以方程组 的任何两个解之间必然相差 
的整倍。
是一个解，同时所有形式为： 
的整数也是方程组 的解。所以方程组所有的解的集合就是：
#include<stdio.h> #include<stdlib.h> #define FORa(i,s,e) for(int i=s;i<=e;i++) #define FORs(i,s,e) for(int i=s;i>=e;i--) using namespace std; const int T=1000; int t,w[T+1],b[T+1],n=1,ans; int Exgcd(int a,int b,int &x,int &y) { int ret,temp; if(!b) { x=1,y=0; return a; } ret=Exgcd(b,a%b,x,y); temp=x; x=y; y=temp-a/b*y; return ret; } int main() { int x,y; scanf("%d",&t); FORa(i,1,t) scanf("%d%d",&w[i],&b[i]),n*=w[i]; FORa(i,1,t) { int m=n/w[i]; Exgcd(w[i],m,x,y); ans=(ans+y*b[i]*m)%n; } if(ans>0) printf("%d",ans); else printf("%d",ans+n); return 0; } /*3 3 2 5 3 7 2*/
原文：https://www.cnblogs.com/SeanOcean/p/11255793.html
