前几天女朋友问我一个题目：一次酒店宴席安排宾客就座吃饭，5人一桌剩4人，7人一桌剩6人，9人一桌剩8人，11人一桌正好。问宴席共有多少人？
一眼看去：中国剩余定理，但是答案和过程的获取的那个揪心啊，让我意识到，当初看过的数论的东西都忘掉了，像这些有可能在密码学中用到的算法知识，看密码学和算导的时候都记得很清楚，也拿实际题目演练过，但是时间一长还是忘记了。现在把功课补一补，写篇文章纪念一下~~~
中国剩余定理：设n=n1*n2*...*nk，其中因子ni两两互质。考虑如下对应关系 a <-> (a1,a2,...,ak)其中 ai = a mod ni
如果a<->(a1,a2,...,ak)，b<->(b1,b2,...,bk)
那么(a+b) mod n <-> ((a1+b1) mod n1, ..., (ak+bk) mod nk)
(a-b) mod n <-> ((a1-b1) mod n1, ... , (ak-bk) mod nk)
(ab) mod n <-> (a1b1 mod n1, ... , akbk mod nk)
这个定理有两个重要推论：
（1）如果n1, n2, ... , nk两两互质，n=n1*n2*...*nk，则对任意整数a1, a2, ... , ak，方程组 x=ai (mod ni) 关于未知量x对模n有唯一解。
（2）如果n1, n2, ... , nk两两互质，n=n1*n2*...*nk，则对所有整数x和a，x=a (mod ni) 当且仅当 x=a (mod n)。
针对这个问题，这个定理怎么用呢？
n1=5,n2=7,n3=9,n4=11。 n=n1*n2*n3*n4 = 3465。我们现在要求的就是a，那么与a的对应关系a1,a2,a3,a4是什么呢？
利用公式：a1 = a mod n1 = 4，a2 = a mod n2 = 6，a3 = a mod n3 = 8，a4 = a mod n4 = 0。
如此，n序列和a序列已经都初始化了。n也计算出来了。问题就转化为知道这些输入，如何能计算出a来。
首先确定m序列，mi是什么呢？定义mi=n/ni。这是一个中间步骤，目的是为了定义c序列ci = mi * (mi
-1 mod ni)。
因为mi和ni互质，mi
-1 mod ni存在。最后计算a 的方法即 a = (a1*c1 + a2*c2 + ... + ak*ck) (mod n)。
具体细节不再多写了，抄书的工作没有意义。有兴趣的朋友们建议多翻书吧。定理书上都有，就针对这一问题，解决方法上代码。
算法实现如下：
1
/** *//**
2
*
3
*/
4
package algorithm.math;
5
6/** *//**
7 * @author Jia Yu
8 * @date 2010-11-11
9 */
10public class ChinaModule 
{
11
12
/** *//**
13 * Return the greatest common divisor.
14
*/
15 public static long gcd( long a, long b )
16 {
17 if( b == 0 )
18 return a;
19 else
20 return gcd( b, a % b );
21 }
22
23 // Internal variables for fullGcd
24 private static long x;
25 private static long y;
26
27 /** *//**
28 * Works back through Euclid's algorithm to find
29 * x and y such that if gcd(a,b) = 1,
30 * ax + by = 1.
31 */
32 private static void fullGcd( long a, long b )
33 {
34 long x1, y1;
35
36 if( b == 0 )
37 {
38 x = 1;
39 y = 0;
40 }
41 else
42 {
43 fullGcd( b, a % b );
44 x1 = x; y1 = y;
45 x = y1;
46 y = x1 - ( a / b ) * y1;
47 }
48 }
49
50 /** *//**
51 * Solve ax == 1 (mod n), assuming gcd( a, n ) = 1.
52 * @return x.
53 */
54 public static long inverse( long a, long n )
55 {
56 fullGcd( a, n );
57 return x > 0 ? x : x + n;
58 }
59
60 public static long china(long[] n, long[] a) {
61 // TODO Auto-generated method stub
62 long n_total = 1L;
63 final int len = n.length;
64 for(int i=0;i<len;i++){
65 n_total *= n[i];
66 }
67
68 long []m = new long[len];
69 for(int i=0;i<len;i++){
70 m[i] = n_total / n[i];
71 }
72
73 long []c = new long[len];
74 for(int i=0;i<len;i++){
75 c[i] = m[i] * inverse(m[i],n[i]);
76 }
77
78 long a_total = 0L;
79 for(int i=0;i<len;i++){
80 a_total += (a[i]*c[i]) % n_total;
81 }
82 a_total %= n_total;
83 return a_total;
84 }
85
86
87 /** *//**
88 * @param args
89 */
90 public static void main(String[] args) {
91 // TODO Auto-generated method stub
92 long n[] = {5,7,9,11};
93 long a[] = {4,6,8,0};
94 //long n[] = {3,5,7};
95 //long a[] = {2,3,2};
96 System.out.println(china(n,a));
97 }
98}
99
其中的GCD方法是欧几里得求最大公约数算法，fullgcd是扩展欧几里得算法，inverse是利用扩展欧几里得方法求乘法逆元的方法，china是通过输入数组求目标数的方法。
最后得到结果2519。即总共2519名宾客。
当时没算出来，过了一会女朋友来短信：“我用excel做出来了”~~~~我狂汗！
