中国剩余定理

代码：
 1 void exgcd(int a, int b, int &d, int &x, int &y)
 2 {
 3     if(!b) { d = a; x = 1; y = 0; }//d为最大公约数 
 4     else { exgcd(b, a%b, d, y, x); y -= x*(a/b); }
 5 }
 6 
 7 int CRT(int a[],int m[],int n)  
 8 {  
 9     int M = 1;  
10     int ans = 0;  
11     for(int i=1; i<=n; i++)  
12         M *= m[i];  
13     for(int i=1; i<=n; i++)  
14     {  
15         int x, y, d;  
16         int Mi = M / m[i];  
17         exgcd(Mi, m[i], d, x, y);
18         ans = (ans + Mi * x * a[i]) % M;  
19     }  
20     if(ans < 0) ans += M;  
21     return ans;  
22 }