Change Dir

先知cd——热爱生活是一切艺术的开始

统计

留言簿(18)

积分与排名

“牛”们的博客

各个公司技术

我的链接

淘宝技术

阅读排行榜

评论排行榜

复习中国剩余定理

前几天女朋友问我一个题目:一次酒店宴席安排宾客就座吃饭,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 */

 4package 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做出来了”~~~~我狂汗!

posted on 2010-11-18 10:10 changedi 阅读(2654) 评论(1)  编辑  收藏 所属分类: 算法

评论

# re: 复习中国剩余定理[未登录] 2010-11-18 13:30 abc

效率虽然低些,可也能算出来。
for (int i=11;i<9999;i=i+11){

if(i%5==4 && i%7==6 && i%9==8){
System.out.println("The number is :" + i);
break;
}

}
The number is :2519
The number is :5984
The number is :9449
  回复  更多评论   


只有注册用户登录后才能发表评论。


网站导航: