资源描述：
《acm中的数学问题_数论部分》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、ACM中的数学问题第一部分：数论主讲人：钱明日期：Dec05,2012引言在ACM竞赛中,经常可以看到数学问题的身影可以是纯数学问题,也可以是需要利用数学上的一些公式,定理,算法来辅助解决的问题会者不难,而不会的选手在赛场上一般很难推出公式或进行证明往往想起来费劲,写起来却很轻松常见的数学问题数论组合数学计算几何博弈论线性代数高等数学线性规划概率统计...本讲内容基本上是最基础的,同时也是ACM竞赛中最常见的数学问题对一些数学公式,定理进行简略地推导或证明,从而加深对它们的理解和认识,也方便记忆往届ACM竞赛中的数学问题数论简而言之,数论就是研究整数的理论在ACM竞赛中,经常用到与数论相
2、关的知识纯数论的题目不多,大部分是和其他类型的问题结合起来的数论的历史自古以来,许许多多的数学家研究过与数论有关的问题直到十九世纪,数论才真正形成了一门独立的学科数论是一门高度抽象的学科,长期处于纯理论研究的状态,曾经被认为是很难有应用价值的随着计算机科学的发展,数论得到了广泛的应用数论主要内容第一部分:同余相关整除的性质欧几里德算法扩展欧几里德算法中国剩余定理第二部分:素数相关算术基本定理欧拉定理素数测试Pollardrho方法数论主要内容第一部分:同余相关整除的性质欧几里德算法扩展欧几里德算法中国剩余定理第二部分:素数相关算术基本定理欧拉定理素数测试Pollardrho方法第一部分同
3、余相关整除的基本性质欧几里德算法扩展欧几里德算法中国剩余定理整除的符号a
4、ba是b的约数（因子），b是a的倍数对于两个不为0的整数整除，被除数的绝对值大于等于除数的绝对值.对于正整数来讲，a
5、b意味着b大，a小整除的基本性质性质1：a
6、b,b
7、c=>a
8、c性质2：a
9、b=>a
10、bc性质3：a
11、b,a
12、c=>a
13、kb±lc性质4：a
14、b,b
15、a=>a=±b整除的基本性质性质5：a=kb±c=>a,b的公因数与b,c的公因数完全相同证明：假设d是b,c的公因数，即d
16、b,d
17、c。利用整除性质3，d整除b,c的线性组合，故d
18、a。所以d是a,b的公因数反之，如果d是a,b的公因数，也能证出d是
19、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共有的倍
20、数60,120,180,240…最大公约数与最小公倍数最小公倍数定义：两个或若干个整数共有倍数中最小的那一个。例子：12，10的最小公倍数最大公约数与最小公倍数的关系lcm(a,b)*gcd(a,b)=a*b所有的公倍数都是最小公倍数的倍数，所有的公约数都是最大公约数的约数。欧几里德算法欧几里德算法(TheEuclideanAlgorithm)又称辗转相除法或者短除法原理:gcd(a,b)=gcd(b,amodb)证明：利用整除性质5(a=kb±c=>a,b的公因数与b,c的公因数完全相同)辗转相除直到两数整除，其中的除数就是要求的最大公约数。欧几里德算法例子：利用欧几里德算法，求63与
21、81的最大公约数步骤：a=81,b=63,amodb=18a←63,b←18,amodb=9a←18,b←9,amodb=0所以9就是63与81的最大公约数欧几里德算法欧几里德算法:whileb>0dor←a%ba←bb←rreturna欧几里德算法欧几里德算法是计算最大公约数的传统算法,也是最简单的算法,效率很高时间复杂度:O(lgn)(最坏情况:斐波那契数列相邻的两项)空间复杂度:O(1)但是,对于大整数来说,取模运算非常耗时欧几里德算法时间复杂度:最坏情况为斐波那契数列相邻的两项体会(13,8)，(12,8)a=k*b+c,c=a-k*b同时满足下面两个条件，序列递减得最慢，即辗转
22、相除法的次数最多k=1最大公约数为1Stein算法原理: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)=(1
