题目描述
自从曹冲搞定了大象以后，曹操就开始琢磨让儿子干些事业，于是派他到中原养猪场养猪，可是曹冲很不高兴，于是在工作中马马虎虎，有一次曹操想知道母猪的数量，于是曹冲想狠狠耍曹操一把。
举个例子，假如有 16头母猪，如果建了 3 个猪圈，剩下 1 头猪就没有地方安家了；如果建造了 5 个猪圈，但是仍然有 1 头猪没有地方去；如果建造了 7 个猪圈，还有 2 头没有地方去。你作为曹总的私人秘书理所当然要将准确的猪数报给曹总，你该怎么办？
输入格式
第一行包含一个整数 n，n<=10表示建立猪圈的次数；
接下来 n 行，每行两个整数ai ，bi(bi<=ai<=1000),表示建立了 ai 个猪圈，有 bi 头猪没有去处。你可以假定ai,aj 互质。
输出格式
输出仅包含一个正整数，即为曹冲至少养猪的数目。
样例
样例输入
3 3 1 5 1 7 2样例输出
16这是一道中国剩余定理的模板题目。
中国剩余定理：一元线性同余方程组问题最早可见于中国南北朝时期（公元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就是合乎条件的最小数.
下面曹冲养猪代码：
#include<iostream> #include<cstdio> using namespace std; long long a[11],b[11],n,m=1,ans=0; void read(){//读入数据 cin>>n; for(long long i=1;i<=n;i++){ cin>>a[i]>>b[i]; m*=a[i]; } } void exgcd(long long a,long long b,long long &d,long long &x,long long &y){ if(b==0){d=a;x=1;y=0;} else{ exgcd(b,a%b,d,x,y); long long t=x;x=y;y=t-a/b*y; } } void intchina(){//中国剩余定理 long long mi,x,y,i,d; for(i=1;i<=n;i++){ mi=m/a[i]; exgcd(mi,a[i],d,x,y); ans=((ans+mi*x*b[i])%m+m)%m; } cout<<ans<<endl; } int main(){ read(); intchina(); return 0; }
