前幾天女朋友問我一個(gè)題目：一次酒店宴席安排賓客就座吃飯，5人一桌剩4人，7人一桌剩6人，9人一桌剩8人，11人一桌正好。問宴席共有多少人？
一眼看去：中國(guó)剩余定理，但是答案和過程的獲取的那個(gè)揪心啊，讓我意識(shí)到，當(dāng)初看過的數(shù)論的東西都忘掉了，像這些有可能在密碼學(xué)中用到的算法知識(shí)，看密碼學(xué)和算導(dǎo)的時(shí)候都記得很清楚，也拿實(shí)際題目演練過，但是時(shí)間一長(zhǎng)還是忘記了。現(xiàn)在把功課補(bǔ)一補(bǔ)，寫篇文章紀(jì)念一下~~~
中國(guó)剩余定理：設(shè)n=n1*n2*...*nk，其中因子ni兩兩互質(zhì)。考慮如下對(duì)應(yīng)關(guān)系 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)
這個(gè)定理有兩個(gè)重要推論：
（1）如果n1, n2, ... , nk兩兩互質(zhì)，n=n1*n2*...*nk，則對(duì)任意整數(shù)a1, a2, ... , ak，方程組 x=ai (mod ni) 關(guān)于未知量x對(duì)模n有唯一解。
（2）如果n1, n2, ... , nk兩兩互質(zhì)，n=n1*n2*...*nk，則對(duì)所有整數(shù)x和a，x=a (mod ni) 當(dāng)且僅當(dāng) x=a (mod n)。
針對(duì)這個(gè)問題，這個(gè)定理怎么用呢？
n1=5,n2=7,n3=9,n4=11。 n=n1*n2*n3*n4 = 3465。我們現(xiàn)在要求的就是a，那么與a的對(duì)應(yīng)關(guān)系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序列已經(jīng)都初始化了。n也計(jì)算出來了。問題就轉(zhuǎn)化為知道這些輸入，如何能計(jì)算出a來。
首先確定m序列，mi是什么呢？定義mi=n/ni。這是一個(gè)中間步驟，目的是為了定義c序列ci = mi * (mi
-1 mod ni)。
因?yàn)閙i和ni互質(zhì)，mi
-1 mod ni存在。最后計(jì)算a 的方法即 a = (a1*c1 + a2*c2 + ... + ak*ck) (mod n)。
具體細(xì)節(jié)不再多寫了，抄書的工作沒有意義。有興趣的朋友們建議多翻書吧。定理書上都有，就針對(duì)這一問題，解決方法上代碼。
算法實(shí)現(xià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方法是歐幾里得求最大公約數(shù)算法，fullgcd是擴(kuò)展歐幾里得算法，inverse是利用擴(kuò)展歐幾里得方法求乘法逆元的方法，china是通過輸入數(shù)組求目標(biāo)數(shù)的方法。
最后得到結(jié)果2519。即總共2519名賓客。
當(dāng)時(shí)沒算出來，過了一會(huì)女朋友來短信：“我用excel做出來了”~~~~我狂汗！
