扩展欧几里得与中国剩余定理.ppt

《扩展欧几里得与中国剩余定理.ppt》由会员分享，可在线阅读，更多相关《扩展欧几里得与中国剩余定理.ppt（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、扩展欧几里得扩展欧几里得&中国剩余定理中国剩余定理BY C-Swimmy准备知识准备知识同余同余 两个整数a，b，若它们除以整数m所得的余数相等，则称a，b对于模m同余记作a b(mod m)读作a同余于b模m，或读作a与b关于模m同余。比如 26 14(mod 12)同余的性质同余的性质性质1 反身性 a a(mod m)2 对称性 若a b(mod m)则b a(mod m)3 传递性 若a b(mod m)，b c(mod m),则a c(mod m)4 同余式相加若a b(mod m)，cd(mod m)，则acbd（mod m）5 同余式相乘 若a b(mod m)，cd(mod m

2、)，则acbd（mod m）线性组合线性组合线性组合是一个线性代数中的概念，代表一些抽象的向量各自乘上一个标量后再相加 欧几里得算法欧几里得算法欧几里德算法又称辗转相除法，用于计算两个正整数a，b的最大公约数。其计算原理 依赖于下面的定理：定理：gcd(a,b)=gcd(b,a mod b)(ab 且a mod b 不为0)证明：a可以表示成a=kb+r，则r=a mod b假设d是a,b的一个公约数，则有d|a,d|b，而r=a-kb，因此d|r因此d也是(b,a mod b)的公约数因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证乘法逆元乘法逆元例如：4

3、关于模7的乘法逆元为多少？4*X1(mod 7)这个方程等价于求一个X和K，满足4X=7K+1其中X和K都是整数。若ax=1 mod f 则称a关于模f的乘法逆元为x。也可表示为ax1(mod f)。当a与f互素时，a关于模f的乘法逆元有唯一解。如果不互素，则无解。如果f为素数，则从1到f-1的任意数都与f互素，即在1到f-1之间都恰好有一个关于模f的乘法逆元。例如，求5关于模14的乘法逆元：14=5*2+45=4+1说明5与14互素，存在5关于14的乘法逆元。1=5-4=5-(14-5*2)=5*3-14因此，5关于模14的乘法逆元为3。其求法可用欧几里德算法Extended Euclid(

4、d，f)算法求d关于模f的乘法逆元d-1，即 d*d-1 mod f=1 1.(X1，X2，X3):=(1，0，f)；(Y1，Y2，Y3):=(0，1，d)2.if(Y3=0)then return d-1=null/无逆元3.if(Y3=1)then return d-1=Y2/Y2为逆元4.Q:=X3 div Y3/整除5.(T1，T2，T3):=(X1-Q*Y1，X2-Q*Y2，X3-Q*Y3)6.(X1，X2，X3):=(Y1，Y2，Y3)7.(Y1，Y2，Y3):=(T1，T2，T3)8.goto 2扩展欧几里德定理扩展欧几里德定理对于不完全为 0 的非负整数 a，b，gcd（a，b

5、）表示 a，b 的最大公约数，必然 在存整数对 x，y，使得 gcd（a，b）=ax+by。求解 x，y的方法的理解设 ab。1，显然当 b=0，gcd（a，b）=a。此时 x=1，y=0；2，ab0 时设 ax1+by1=gcd(a,b);bx2+(a mod b)y2=gcd(b,a mod b);根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);则:ax1+by1=bx2+(a mod b)y2;即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;根据恒等定理得：x1=y2;y1=x2-(a/b)*y2;这样我们就得到了求解

6、 x1,y1 的方法：x1，y1 的值基于 x2，y2.上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以结束。PROBLEM 1 POJ1006BiorhythmsTime Limit:1000MSMemory Limit:10000KDescriptionSome people believe that there are three cycles in a persons life that start the day he or she is born.These three cycles are the physical,emotional,a

7、nd intellectual cycles,and they have periods of lengths 23,28,and 33 days,respectively.There is one peak in each period of a cycle.At the peak of a cycle,a person performs at his or her best in the corresponding field(physical,emotional or mental).For example,if it is the mental curve,thought proces

8、ses will be sharper and concentration will be easier.Since the three cycles have different periods,the peaks of the three cycles generally occur at different times.We would like to determine when a triple peak occurs(the peaks of all three cycles occur in the same day)for any person.For each cycle,y

9、ou will be given the number of days from the beginning of the current year at which one of its peaks(not necessarily the first)occurs.You will also be given a date expressed as the number of days from the beginning of the current year.You task is to determine the number of days from the given date t

10、o the next triple peak.The given date is not counted.For example,if the given date is 10 and the next triple peak occurs on day 12,the answer is 2,not 3.If a triple peak occurs on the given date,you should give the number of days to the next occurrence of a triple peak.InputYou will be given a numbe

11、r of cases.The input for each case consists of one line of four integers p,e,i,and d.The values p,e,and i are the number of days from the beginning of the current year at which the physical,emotional,and intellectual cycles peak,respectively.The value d is the given date and may be smaller than any

12、of p,e,or i.All values are non-negative and at most 365,and you may assume that a triple peak will occur within 21252 days of the given date.The end of input is indicated by a line in which p=e=i=d=-1.OutputFor each test case,print the case number followed by a message indicating the number of days

13、to the next triple peak,in the form:Case 1:the next triple peak occurs in 1234 days.Use the plural form days even if the answer is 1.Sample Intput0 0 0 00 0 0 1005 20 34 3254 5 6 7283 102 23 320203 301 203 40-1-1-1-1Sample OutputCase 1:the next triple peak occurs in 21252 days.Case 2:the next triple

14、 peak occurs in 21152 days.Case 3:the next triple peak occurs in 19575 days.Case 4:the next triple peak occurs in 16994 days.Case 5:the next triple peak occurs in 8910 days.Case 6:the next triple peak occurs in 10789 days.Sample Input&Output 中国剩余定理（孙子定理）三数为a b c余数分别为 m1 m2 m3,%为求余计算,&意为“且”1、分别找出能被两个

15、数整除，而满足被第三个整除余一的最小的数。k1%b=k1%c=0&k1%a=1;k2%a=k2%c=0&k2%b=1;k3%a=k3%b=0&k3%c=1;2、将三个未知数乘对应数字的余数再加起来，减去这三个数的最小公倍数的整数倍即得结果。Answer=k1*m1+k2*m2+k3*m3-P*(a*b*c);P为满足Answer 0的最大整数；或者 Answer=(k1*m1+k2*m2+k3*m3)%(a*b*c);证明证明令T1=k1*m1,T2=k2*m2,T3=k3*m3;因为 k1%a=1；所以 T1%a=m1;对于 a，已知：T2%a=0,T3%a=0,T1%a=m1;所以：Answer%a=m1;因为：T1%b=0,T3%b=0,T2%b=m2=Answer%b=m2同理：Answer%c=m3;又因为 a*b*c能同时整除 a b c，所以Answer P*(a*b*c）也是题目的解；所以Answer是题目的解，又Answer=Answer%(a*b*c），所以Answer为最小解.PROBLEM 2 POJ2891十分类似的问题，有些难度，自己研究研究，解题报告可参考标程