LightOJ 1319 Monkey Tradition(中国剩余定理)

题目链接：https://vjudge.net/contest/28079#problem/U

题目大意：给你n（n<12）行，每行有pi，ri，求一个数ans满足ans%pi=ri（i从1~n）。

解题思路：就是解同余方程组：比如第一组样例：

5 4

7 6

11 3

就是要我们求一个x满足下列同余方程组：

x≡4(mod5)

x≡6(mod7)

x≡11(mod3)

然后自己看这里吧写了解释http://www.cnblogs.com/fu3638/p/7453419.html，是CRT裸题

代码：

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 using namespace std;
 5 typedef long long LL;
 6 const int N=20;
 7 LL m[N],a[N],n;
 8 //扩展欧几里得 
 9 void exgcd(LL a,LL b,LL &x,LL &y){
10     if(!b){
11         x=1;
12         y=0;
13     }
14     else{
15         exgcd(b,a%b,y,x);
16         y-=(a/b)*x;
17     }    
18 }
19 //中国剩余余定理 
20 LL CRT(){
21     LL M=1;
22     for(int i=1;i<=n;i++)
23         M*=m[i];
24     LL ans=0;
25     for(int i=1;i<=n;i++){
26         LL x,y,Mi;
27         Mi=M/m[i];
28         exgcd(Mi,m[i],x,y);
29         ans=(ans+a[i]*Mi*x)%M;
30     }
31     if(ans<0) ans+=M;
32     return ans;    
33 }
34 
35 int main(){
36     int T;
37     scanf("%d",&T);
38     int cas=0;
39     while(T--){
40         scanf("%d",&n);
41         for(int i=1;i<=n;i++){
42             scanf("%lld%lld",&m[i],&a[i]);
43         }
44         printf("Case %d: %lld
",++cas,CRT());
45     }
46 }