1 /*
 2 mi之间互质
 3 同余方程组 ：
 4 设正整数m1.m2.mk两两互素，则方程组
 5 x ≡ a1 (mod m1)
 6 x ≡ a2 (mod m2)
 7 x ≡ a3 (mod m3)
 8 .
 9 .
10 x ≡ ak (mod mk)
11 有整数解，
12 解为  x ≡ (a1 * M1 * 1/M1 + a2 * M2 * 1/M2 + a3 * M3 * 1/M3 + …… +ak * Mk * 1/Mk) mod M
13 其中 M = M1 * M2 * M3 * …… * Mk, Mi为M/mi, 1/Mi为Mi的逆元
14 */
15 
16 void exgcd(int a, int b, int &x, int &y)
17 {
18     if(b == 0) {
19         x = 1;
20         y = 0;
21         return a;
22     }
23     exgcd(b, a % b, x, y);
24     int t = x;
25     x = y;
26     y = t - a / b * y;
27     return r;
28 }
29 
30 LL CRT(int m[], int a[], int n)  // m 是 mod 的数, a 是余数, n 是方程组组数
31 {
32     LL M = 1, ans = 0;
33     for(int i = 0; i < n; i++)
34         M *= m[i];
35     for(int i = 0; i < n; i++) {
36         int x, y;
37         LL Mi = M / m[i];
38         exgcd(Mi, m[i], x, y); //求出的 x 即 Mi 的逆元
39         ans = (ans + Mi * a[i] * x % M + M) % M;
40     }
41     return ans;
42 }