曹冲养猪

曹冲养猪(cao)

题目描述

自从曹冲搞定了大象以后，曹操就开始捉摸让儿子干些事业，于是派他到中原养猪场养猪，可是曹冲满不高兴，于是在工作中马马虎虎，有一次曹操想知道母猪的数量，于是曹冲想狠狠耍曹操一把。举个例子，假如有16头母猪，如果建了3个猪圈，剩下1头猪就没有地方安家了。如果建造了5个猪圈，但是仍然有1头猪没有地方去，然后如果建造了7个猪圈，还有2头没有地方去。你作为曹总的私人秘书理所当然要将准确的猪数报给曹总，你该怎么办？

输入

第一行包含一个整数n (n <= 10) – 建立猪圈的次数，解下来n行，每行两个整数ai, bi( bi <= ai <= 1000), 表示建立了ai个猪圈，有bi头猪没有去处。你可以假定ai,aj互质.

输出

输出包含一个正整数，即为曹冲至少养母猪的数目。

样例输入

3 1

5 1

7 2

样例输出

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 #define N 5050
 5 typedef long long LL;
 6 LL m[N];
 7 LL M=1,n,ans;
 8 LL t[N],Mn[N],MM[N];
 9  
10 LL exgcd(LL a,LL b,LL &x,LL &y)
11 {
12     if(b==0)
13     {
14         x=1,y=0;return a;   
15     }
16     else
17     {
18         LL t=exgcd(b,a%b,y,x);
19         y-=x*(a/b);
20         return t;
21     }
22 }
23  
24 LL CRT()
25 {
26     LL temp;
27     for(LL i=1;i<=n;i++)
28     {
29         MM[i]=M/m[i]; //MM[i]就表示m数组中除了下标为i元素的所有其它元素的乘积
30         LL k=exgcd(MM[i],m[i],Mn[i],temp);
31         ans+=(MM[i]*Mn[i]*t[i]);
32     }
33     return ((ans%M)+M)%M;
34 }
35  
36 int main()
37 {
38     freopen("cao.in","r",stdin);
39     freopen("cao.out","w",stdout);
40     cin>>n;
41     for(LL i=1;i<=n;i++)
42     {
43         scanf("%d%d",&m[i],&t[i]);
44         M*=m[i]; //各个m[i]互质 
45     }
46      
47     cout<<CRT()<<endl;
48      
49     return 0;     
50 }

**exgcd &&中国剩余孙子定理。

然而我可能一个都不会，待我明天看懂同余方程and后天看懂exgcd再来补充这道题叭，睡了，晚安