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

ACM中的数学问题,第一部分：数论,主讲人：钱明日期：Dec05,2012,引言,在ACM竞赛中,经常可以看到数学问题的身影可以是纯数学问题,也可以是需要利用数学上的一些公式,定理,算法来辅助解决的问题会者不难,而不会的选手在赛场上一般很难推出公式或进行证明往往想起来费劲,写起来却很轻松,常见的数学问题,数论组合数学计算几何博弈论线性代数高等数学线性规划概率统计.,本讲内容,基本上是最基础的,同时也是ACM竞赛中最常见的数学问题对一些数学公式,定理进行简略地推导或证明,从而加深对它们的理解和认识,也方便记忆往届ACM竞赛中的数学问题,数论,简而言之,数论就是研究整数的理论在ACM竞赛中,经常用到与数论相关的知识纯数论的题目不多,大部分是和其他类型的问题结合起来的,数论的历史,自古以来,许许多多的数学家研究过与数论有关的问题直到十九世纪,数论才真正形成了一门独立的学科数论是一门高度抽象的学科,长期处于纯理论研究的状态,曾经被认为是很难有应用价值的随着计算机科学的发展,数论得到了广泛的应用,数论主要内容,第一部分:同余相关整除的性质欧几里德算法扩展欧几里德算法中国剩余定理第二部分:素数相关算术基本定理欧拉定理素数测试Pollardrho方法,数论主要内容,第一部分:同余相关整除的性质欧几里德算法扩展欧几里德算法中国剩余定理第二部分:素数相关算术基本定理欧拉定理素数测试Pollardrho方法,第一部分同余相关,整除的基本性质欧几里德算法扩展欧几里德算法中国剩余定理,整除的符号,a|ba是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所有的公倍数都是最小公倍数的倍数，所有的公约数都是最大公约数的约数。,欧几里德算法,欧几里德算法(TheEuclideanAlgorithm)又称辗转相除法或者短除法原理:gcd(a,b)=gcd(b,amodb)证明：利用整除性质5(a=kbc=a,b的公因数与b,c的公因数完全相同)辗转相除直到两数整除，其中的除数就是要求的最大公约数。,欧几里德算法,例子：利用欧几里德算法，求63与81的最大公约数步骤：a=81,b=63,amodb=18a63,b18,amodb=9a18,b9,amodb=0所以9就是63与81的最大公约数,欧几里德算法,欧几里德算法:whileb0dora%babbrreturna,欧几里德算法,欧几里德算法是计算最大公约数的传统算法,也是最简单的算法,效率很高时间复杂度: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算法(假设00doifa偶,b偶thenaa1bb1rr+1elseifa偶,b奇thenaa1elseifa奇,b偶thenbb1elseifa奇,b奇thena(a-b)1ifabthen交换a,breturna=1)，则a与b也互素a1(modb)，则a与b互素,筛法,目标:求出n以内的所有质数算法步骤:初始时容器内为2到n的所有正整数取出容器中最小的数p,p一定是质数,删去p的所有倍数(注:只需从p2开始删除即可)重复上述步骤直到容器为空,筛法,优点:算法简单,空间上只需要一个O(n)的bool数组缺陷:一个数可能被重复删去多次,影响效率例:在p=2,3,5,7时均会尝试删除210一般的,若x有k个质因子,则x会被处理k次,筛法(改进),改进:初始时容器内为2到n的所有正整数取出容器中最小的数p,p一定是质数删去所有的pi,令q为第一个未被删除的数,保留q,删去所有的piq,再令q为下一个未被删除的数.直到q遍历所有未被删除的数为止(这一步骤可以把最小质因数为p的所有数删去)重复上面两个步骤直到容器为空,筛法(改进),用bool数组+双向链表实现,空间复杂度仍为O(n)小优化:初始时只加入奇数,算术基本定理,任何一个大于1的自然数n,都可以唯一分解成有限个质数的乘积n=p1r1p2r2.pkrkp1p2.pk均为质数,r1,r2,.rk均为正整数,欧拉函数,记(x)为与x互质且小等于x的正整数个数设x=p1r1p2r2.pkrk(x)=x*(1-1/p1)*(1-1/p2)*.*(1-1/pk)或(x)=p1(r1-1)(p1-1)p2(r2-1)(p2-1).pk(rk-1)(pk-1)递推形式:质数p满足p|x若p2|x,则(x)=(x/p)*p否则(x)=(x/p)*(p-1),欧拉函数,证明:若p为质数,则(p)=p-1(pr)=pr(1-1/p)=p(r-1)(p-1)若a,b互质,则(ab)=(a)(b)扩展:n的所有因子之和(p10+.+p1r1)(p20+.+p2r2).(pk0+.+pkrk),欧拉定理,若a和m互质,则a(m)1(modm)证明:设(m)个正整数r1,r2,.,r(m)满足:ri与m互质,对于任意ij,rirj(modm)由于a与m互质,可以证明ar1,ar2,.,ar(m)依然满足上述条件这样就有(ar1)(ar2).(ar(m)r1r2.r(m)(modm)而(ar1)(ar2).(ar(m)a(m)r1r2.r(m)(modm)两边同时约去r1r2.r(m)即得到欧拉定理,素数测试,费马小定理:若p为素数,则对于任意小于p的正整数a,有a(p-1)1(modp)证明:欧拉定理的特例(m为质数)问题:只是必要条件,不是充分条件反例:561,1105,1729.,素数测试,二次探测定理:若p为素数,a21(modp)小于p的正整数解只有1和p-1满足费马小定理和二次探测定理的数可以确定是素数,Miller-Rabin算法,Miller-Rabin算法(n为待判定数):令n-1=m*2j,m为奇数随机在2(n-1)之间取一个整数b,令v=bm对v平方,当v=1时,若上一次的v既不是1也不是(n-1),由二次探测定理,n不是素数,退出;循环j次得到b(n-1)v=1,满足费马小定理,通过测试;否则n一定不是素数选取几个不同的b进行多次测试,素数测试,Miller-Rabin只能算一种测试,因为通过测试的数不一定是素数,非素数通过测试的概率大约是1/4虽然一次测试的结果不一定令人满意,但五六次随机测试基本可以保证正确率超过99.9%,大整数分解,至今仍是世界难题在密码学中起着至关重要的作用试除法,Fermat方法,Pollard方法Pollardrho方法,Pollardrho方法,原理:设n为待分解的大整数用某种方法生成两个整数a和b,计算p=gcd(a-b,n),直到p不为1或a,b出现循环为止若p=n,则n为质数,否则p为n的一个约数,Pollardrho方法,算法步骤:选取一个小的随机数x1迭代生成xi=x(i-1)2+k,一般取k=1,若序列出现循环则退出计算p=gcd(x(i-1)-xi,n),若p=1,返回上一步继续迭代;否则跳出迭代过