ACM中的数学问题_数论部分.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二层,第三层,第四层,第五层,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,ACM,中的数学问题,第一部分：数论,主讲人：钱明,日期：,Dec 05,2012,引言,在,ACM,竞赛中,经常可以看到数学问题的身影,可以是纯数学问题,也可以是需要利用数学上的一些公式,定理,算法来辅助解决的问题,会者不难,而不会的选手在赛场上一般很难推出公式或进行证明,往往想起来费劲,写起来却很轻松,常见的数学问题,数论,组合数学,计算几何,博弈论,线性代数,高等数学,线性规划,概率统计,.,本讲内容,基本上是最基础的,同时也是,ACM,竞赛中最常见的数学问题,对一些数学公式,定理进行简略地推导或证明,从而加深对它们的理解和认识,也方便记忆,往届,ACM,竞赛中的数学问题,数论,简而言之,数论就是研究整数的理论,在,ACM,竞赛中,经常用到与数论相关的知识,纯数论的题目不多,大部分是和其他类型的问题结合起来的,数论的历史,自古以来,许许多多的数学家研究过与数论有关的问题,直到十九世纪,数论才真正形成了一门独立的学科,数论是一门高度抽象的学科,长期处于纯理论研究的状态,曾经被认为是很难有应用价值的,随着计算机科学的发展,数论得到了广泛的应用,数论主要内容,第一部分,:,同余相关,整除的性质,欧几里德算法,扩展欧几里德算法,中国剩余定理,第二部分,:,素数相关,算术基本定理,欧拉定理,素数测试,Pollard rho,方法,数论主要内容,第一部分,:,同余相关,整除的性质,欧几里德算法,扩展欧几里德算法,中国剩余定理,第二部分,:,素数相关,算术基本定理,欧拉定理,素数测试,Pollard rho,方法,第一部分 同余相关,整除的基本性质,欧几里德算法,扩展欧几里德算法,中国剩余定理,整除的符号,a|b,a,是,b,的约数（因子），,b,是,a,的倍数,对于两个不为,0,的整数整除，被除数的绝对值大于等于除数的绝对值,.,对于正整数来讲，,a|b,意味着,b,大，,a,小,整除的基本性质,性质,1,：,a|b,b|c,=,a|c,性质,2,：,a|b,=,a|bc,性质,3,：,a|b,a|c,=,a|kblc,性质,4,：,a|b,b|a,=a=b,整除的基本性质,性质,5,：,a=,kbc,=,a,b,的公因数与,b,c,的公因数完全相同,证明：,假设,d,是,b,c,的公因数，即,d|b,d|c,。,利用整除性质,3,，,d,整除,b,c,的线性组合，故,d|a,。,所以,d,是,a,b,的公因数,反之，如果,d,是,a,b,的公因数，也能证出,d,是,b,c,的公因数,第一部分 同余相关,整除的基本性质,欧几里德算法,扩展欧几里德算法,中国剩余定理,请写出,12,，,30,共有的约数,请写出,12,，,30,共有的约数,1,请写出,12,，,30,共有的约数,1,2,请写出,12,，,30,共有的约数,1,2,3,请写出,12,，,30,共有的约数,1,2,3,6.,最大公约数与最小公倍数,最大公约数,定义：,两个或若干个整数的公约数中最大的那个公约数,例子：,12,，,30,的最大公约数,如何求两个整数的最大公约数：,辗转相除法（扩展版）,Stein,算法,请写出,12,，,10,共有的倍数,请写出,12,，,10,共有的倍数,60,请写出,12,，,10,共有的倍数,60,120,请写出,12,，,10,共有的倍数,60,120,180,请写出,12,，,10,共有的倍数,60,120,180,240,最大公约数与最小公倍数,最小公倍数,定义：,两个或若干个整数共有倍数中最小的那一个。,例子：,12,，,10,的最小公倍数,最大公约数与最小公倍数的关系,lcm(a,b,),*,gcd(a,b,)=a*b,所有的公倍数都是最小公倍数的倍数，所有的公约数都是最大公约数的约数。,欧几里德算法,欧几里德算法(The Euclidean Algorithm),又称辗转相除法,或者 短除法,原理,:,gcd(a,b,)=,gcd(b,a,mod b),证明：,利用整除性质,5(a=,kbc,=,a,b,的公因数与,b,c,的公因数完全相同,),辗转相除直到两数整除，其中的除数就是要求的最大公约数。,欧几里德算法,例子：利用欧几里德算法，求,63,与,81,的最大公约数,步骤：,a=81,b=63,a mod b=18,a 63,b 18,a mod b=9,a 18,b 9,a mod b =0,所以,9,就是,63,与,81,的最大公约数,欧几里德算法,欧几里德算法,:,while b0,do,ra%b,ab,br,return a,欧几里德算法,欧几里德算法是计算最大公约数的传统算法,也是最简单的算法,效率很高,时间复杂度,:,O(lgn,)(,最坏情况,:,斐波那契数列相邻的两项,),空间复杂度,:O(1),但是,对于大整数来说,取模运算非常耗时,欧几里德算法,时间复杂度,:,最坏情况为斐波那契数列相邻的两项,体会,(13,8),，,(12,8),a=k*b+c,c=a-k*b,同时满足下面两个条件，序列递减得最慢，即辗转相除法的次数最多,k=1,最大公约数为,1,Stein,算法,原理,:,gcd(ka,kb,)=k*,gcd(a,b,),当,k=2,时,说明两个偶数的最大公约数必然能被,2,整除,当,k,与,b,互素时，,gcd(ka,b,)=,gcd(a,b,),当,k=2,时，说明计算一个偶数和一个奇数的最大公约数时，可以先将偶数除以,2,(a,b)=(b,a-b),Stein,算法,例子：,两个都为偶数,(10,8)=2*(5,4),一个奇数，一个 偶数,(15,12)=,(15,6),两个都是奇数,(25,15)=(15,5),Stein,算法,Stein,算法,(,假设,0=b0,do if a,偶,b,偶,then,aa,1,bb,1 rr+1,else if a,偶,b,奇,then,aa,1,else if a,奇,b,偶,then,bb,1,else if a,奇,b,奇,then,a(a-b,)1,if ab then,交换,a,b,return a=1),，则,a,与,b,也互素,a,1(mod b),，则,a,与,b,互素,筛法,目标,:,求出,n,以内的所有质数,算法步骤,:,初始时容器内为,2,到,n,的所有正整数,取出容器中最小的数,p,p,一定是质数,删去,p,的所有倍数,(,注,:,只需从,p,2,开始删除即可,),重复上述步骤直到容器为空,筛法,优点,:,算法简单,空间上只需要一个,O(n),的,bool,数组,缺陷,:,一个数可能被重复删去多次,影响效率,例,:,在,p=2,3,5,7,时均会尝试删除,210,一般的,若,x,有,k,个质因子,则,x,会被处理,k,次,筛法,(,改进,),改进,:,初始时容器内为,2,到,n,的所有正整数,取出容器中最小的数,p,p,一定是质数,删去所有的,p,i,令,q,为第一个未被删除的数,保留,q,删去所有的,p,i,q,再令,q,为下一个未被删除的数,.,直到,q,遍历所有未被删除的数为止,(,这一步骤可以把最小质因数为,p,的所有数删去,),重复上面两个步骤直到容器为空,筛法,(,改进,),用,bool,数组,+,双向链表实现,空间复杂度仍为,O(n),小优化,:,初始时只加入奇数,算术基本定理,任何一个大于,1,的自然数,n,都可以唯一分解成有限个质数的乘积,n=p,1,r1,p,2,r2,.p,k,rk,p,1,p,2,.p,k,均为质数,r,1,r,2,.r,k,均为正整数,欧拉函数,记,(x)为与x互质且小等于x的正整数个数,设x=p,1,r1,p,2,r2,.p,k,rk,(x)=x*(1-1/p,1,)*(1-1/p,2,)*.*(1-1/p,k,)或,(x)=p,1,(r1-1),(p,1,-1)p,2,(r2-1),(p,2,-1).p,k,(rk-1),(p,k,-1),递推形式:质数p满足p|x,若p,2,|x,则,(x)=,(x/p)*p,否则,(x)=,(x/p)*(p-1),欧拉函数,证明:,若p为质数,则,(p)=p-1,(p,r,)=p,r,(1-1/p)=p,(r-1),(p-1),若a,b互质,则,(ab)=,(a),(b),扩展:n的所有因子之和,(p,1,0,+.+p,1,r1,)(p,2,0,+.+p,2,r2,).(p,k,0,+.+p,k,rk,),欧拉定理,若a和m互质,则,a,(m),1(mod m),证明:,设,(m)个正整数r,1,r,2,.,r,(m),满足:r,i,与m互质,对于任意ij,r,i,r,j,(mod m),由于a与m互质,可以证明ar,1,ar,2,.,ar,(m),依然满足上述条件,这样就有(ar,1,)(ar,2,).(ar,(m),),r,1,r,2,.r,(m),(mod m),而(ar,1,)(ar,2,).(ar,(m),),a,(m),r,1,r,2,.r,(m),(mod m),两边同时约去r,1,r,2,.r,(m),即得到欧拉定理,素数测试,费马小定理,:,若,p,为素数,则对于任意小于,p,的正整数,a,有,a,(p-1),1(mod p),证明,:,欧拉定理的特例,(m,为质数,),问题,:,只是必要条件,不是充分条件,反例,:561,1105,1729.,素数测试,二次探测定理,:,若,p,为素数,a,2,1(mod p),小于,p,的正整数解只有,1,和,p-1,满足费马小定理和二次探测定理的数可以确定是素数,Miller-Rabin,算法,Miller-Rabin,算法,(n,为待判定数,):,令,n-1=m*2,j,m,为奇数,随机在,2(n-1),之间取一个整数,b,令,v=b,m,对,v,平方,当,v=1,时,若上一次的,v,既不是,1,也不是,(n-1),由二次探测定理,n,不是素数,退出,;,循环,j,次得到,b,(n-1),v=1,满足费马小定理,通过测试,;,否则,n,一定不是素数,选取几个不同的,b,进行多次测试,素数测试,Miller-Rabin,只能算一种测试,因为通过测试的数不一定是素数,非素数通过测试的概率大约是,1/4,虽然一次测试的结果不一定令人满意,但五六次随机测试基本可以保证正确率超过,99.9%,大整数分解,至今仍是世界难题,在密码学中起着至关重要的作用,试除法,Fermat,方法,Pollard,方法,Pollard rho,方法,Pollard rho,方法,原理,:,设,n,为待分解的大整数,用某种方法生成两个整数,a,和,b,计算,p=gcd(a-b,n),直到,p,不为,1,或,a,b,出现循环为止,若,p=n,则,n,为质数,否则,p,为,n,的一个约数,Pollard rho,方法,算法步骤,:,选取一个小的随机数,x,1,迭代生成,x,i,=x,(i-1),2,+k,一般取,k=1,若序列出现循环则退出,计算,p=gcd(x,(i-1),-x,i,n),若,p=1,返回上一步继续迭代,;,否则跳出迭代过程,若,p=n,则,n,为素数,;,否则,p,为,n,的一个约数并递归分解,p,和,n/p,Pollard rho,方法,可以在,(sqrt(p),的期望时间内找出,n,的一个小因子,p,但对于因子很少,因子值很大的大整数,n,该方法依然不是很有效,数论小结,前面的这些都是一些初等数论的知识,可以看出,数论所研究的内容,很大一部分都是和素数紧密联系的,.,因此,数论是名副其实的,素论,这些算法代码量都不大,但如果没有准备好模版的话,往往会忽略一些细节,