曹冲养猪

本题是一道中国剩余定理的板子题，之前考的时候一次过了，后来也没有总结，于是这回就跪了。。。

中国剩余定理用于求解多组同余方程：

x≡b1(mod a1)

x≡b2(mod a2)

......

x≡bn(mod an)

我们定义M是所有a的积，M=a1*a2*a3*...*an

对于每一个解，在方程两边同时乘以M/ai　　得到x*M/ai≡M*bi/ai (mod ai)

我们求解出这个不定方程的答案，这个可以利用扩欧，由于扩欧解的是x*M/ai≡1(mod ai)，所以把求到的答案乘以M*bi/ai/就好了

那么我们得到了一组解的答案，而通解就是x+k*M，由于要求最小正整数解，常规取模就好了。

最后，附上本体代码：

 1 #include<cstdio> 
 2 //Debug Yufenglin
 3 #define debugj printf("Running
");
 4 #define debugp1(x) printf("%d
",x);
 5 #define debugp2(x,y) printf("%d %d
",x,y);
 6 #define debugp3(x,y,z) printf("%d %d %d
",x,y,z);
 7 
 8 //Standfor Yufenglin
 9 #define LL long long
10 #define LB long double
11 #define reg register
12 #define il inline
13 #define inf 1e8
14 #define maxn 10
15 
16 LL n,a[maxn+5],b[maxn+5];
17 
18 void exgcd(LL c,LL d,LL &x,LL &y)
19 {
20     if(d==0)
21     {
22         x=1,y=0;
23         return;
24     }
25     exgcd(d,c%d,x,y);
26     LL x1=x,y1=y;
27     x=y1;
28     y=x1-y1*(c/d);
29 }
30 LL China()
31 {
32     LL lcm=1,ans=0,x,y;
33     for(int i=1;i<=n;i++)
34     {
35         lcm*=a[i];
36     }
37     for(int i=1;i<=n;i++)
38     {
39         LL temp=lcm/a[i];
40         exgcd(temp,a[i],x,y);
41         x=(x%a[i]+a[i])%a[i];
42         ans+=x*temp*b[i];
43     }
44     return (ans+lcm)%lcm;
45 }
46 int main()
47 {
48     scanf("%lld",&n);
49     for(int i=1;i<=n;i++)
50     {
51         scanf("%lld%lld",&a[i],&b[i]);
52     }
53     printf("%lld
",China());
54     return 0;
55 }