数论-扩展中国剩余定理

求解 n 个同余方程

x ≡ Ci (mod Mi)

推荐一下讲证明的文章：

1.https://www.cnblogs.com/TheRoadToTheGold/p/8458326.html 很简洁易懂。

2.http://blog.csdn.net/clove_unique/article/details/54571216 排版不太好；这篇文章还讲了扩展卢卡斯 (Lucas) 定理。

可以用滚动数组优化空间，但我的代码里没这么写。

 1 void China()
 2 {
 3     scanf("%lld", &n);
 4     for (i = 1; i <= n; ++i)
 5         scanf("%lld%lld", &M[i], &C[i]);
 6     bool flag = false;
 7     for (i = 2; i <= n; ++i) {
 8         LL m1 = M[i-1], m2 = M[i], c1 = C[i-1], c2 = C[i];
 9         LL t = gcd(m1, m2);
10         if ((c2-c1) % t) { flag = true; break; }
11         M[i] = m1*m2 / t;
12         C[i] = Inv(m1/t, m2/t) * (c2-c1)/t % (m2/t) * m1 + c1;
13         C[i] = (C[i]%M[i]+M[i]) % M[i];
14     }
15     if (flag) { printf("-1
"); continue; }
16     printf("%lld
", C[n]);
17 }

模板题 POJ2891

 1 #include <stdio.h>
 2 
 3 typedef long long LL;
 4 
 5 const int _N = 1200;
 6 
 7 LL C[_N], M[_N];
 8 
 9 void exgcd(LL m, LL n, LL &x, LL &y, LL &d)
10 {
11     if (n) { exgcd(n, m%n, y, x, d); y -= m/n*x; return; }
12     x = 1, y = 0, d = 1;
13     return;
14 }
15 
16 LL gcd(LL t1, LL t2) { return t2 ? gcd(t2, t1 % t2) : t1; }
17 
18 LL Inv(LL v, LL p)
19 {
20     LL x, y, d;
21     exgcd(v, p, x, y, d);
22     x = (x%p+p)%p;
23     if (!x) x = p;
24     return x;
25 }
26 
27 int main()
28 {
29     LL n, i;
30     while (~scanf("%lld", &n)) {
31         for (i = 1; i <= n; ++i)
32             scanf("%lld%lld", &M[i], &C[i]);
33         bool flag = false;
34         for (i = 2; i <= n; ++i) {
35             LL m1 = M[i-1], m2 = M[i], c1 = C[i-1], c2 = C[i];
36             LL t = gcd(m1, m2);
37             if ((c2-c1) % t) { flag = true; break; }
38             M[i] = m1*m2 / t;
39             C[i] = Inv(m1/t, m2/t) * (c2-c1)/t % (m2/t) * m1 + c1;
40             C[i] = (C[i]%M[i]+M[i]) % M[i];
41         }
42         if (flag) { printf("-1
"); continue; }
43         printf("%lld
", C[n]);
44     }
45     return 0;
46 }