acm中的数学问题-march+10-总结.ppt

《acm中的数学问题-march+10-总结.ppt》由会员分享，可在线阅读，更多相关《acm中的数学问题-march+10-总结.ppt（97页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、本讲内容l基本上是最基础的,同时也是ACM竞赛中最常见的数学问题l对一些数学公式,定理进行简略地推导或证明,从而加深对它们的理解和认识,也方便记忆l往届ACM竞赛中的数学问题数论l简而言之,数论就是研究整数的理论l在ACM竞赛中,经常用到与数论相关的知识l纯数论的题目不多,大部分是和其他类型的问题结合起来的数论的历史l自古以来,许许多多的数学家研究过与数论有关的问题l直到十九世纪,数论才真正形成了一门独立的学科l数论是一门高度抽象的学科,长期处于纯理论研究的状态,曾经被认为是很难有应用价值的l随着计算机科学的发展,数论得到了广泛的应用数论主要内容第一部分:同余相关 整除的性质 欧几里德算法 扩

2、展欧几里德算法 中国剩余定理第二部分:素数相关 算术基本定理 欧拉定理 素数测试 Pollard rho方法数论主要内容第一部分:同余相关 整除的性质 欧几里德算法 扩展欧几里德算法 中国剩余定理第二部分:素数相关 算术基本定理 欧拉定理 素数测试 Pollard rho方法第一部分 同余相关 l整除的基本性质l欧几里德算法l扩展欧几里德算法l中国剩余定理整除的符号la|ba是b的约数（因子），b是a的倍数对于两个不为0的整数整除，被除数的绝对值大于等于除数的绝对值. 对于正整数来讲，a|b 意味着b大，a小整除的基本性质l性质1：a|b,b|c = a|cl性质2 ：a|b = a|bcl性

3、质3 ： a|b,a|c = a|kblcl性质4 ： a|b,b|a = a=b整除的基本性质l性质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的公因数第一部分 同余相关 l整除的基本性质l欧几里德算法l扩展欧几里德算法l中国剩余定理请写出12，30共有的约数请写出12，30共有的约数1,请写出12，30共有的约数1, 2, 请写出12，30共有的约数1, 2, 3,请写出1

4、2，30共有的约数1, 2, 3, 6.最大公约数与最小公倍数l最大公约数定义：两个或若干个整数的公约数中最大的那个公约数例子：12，30的最大公约数如何求两个整数的最大公约数：如何求两个整数的最大公约数：辗转相除法（扩展版）辗转相除法（扩展版）Stein 算法算法请写出请写出12，10共有的倍数共有的倍数请写出12，10共有的倍数60,请写出12，10共有的倍数60, 120, 请写出12，10共有的倍数60, 120, 180, 请写出12，10共有的倍数60, 120, 180, 240最大公约数与最小公倍数l最小公倍数定义：两个或若干个整数共有倍数中最小的那一个。例子：12，10的最小

5、公倍数l最大公约数与最小公倍数的关系lcm(a,b) * * gcd(a,b)=a*bl所有的公倍数都是最小公倍数的倍数，所有的公约数都是最大公约数的约数。欧几里德算法l欧几里德算法 (The Euclidean Algorithm)又称辗转相除法 或者 短除法原理: gcd(a,b) = gcd(b,a mod b) 证明：利用整除性质5(a=kbc = a,b的公因数与b,c的公因数完全相同)辗转相除直到两数整除，其中的除数就是要求的最大公约数。欧几里德算法l例子：利用欧几里德算法，求63与81的最大公约数步骤：a = 81, b = 63, a mod b = 18a 63, b 18,

6、 a mod b = 9 a 18, b 9, a mod b = 0所以9就是63与81的最大公约数欧几里德算法l欧几里德算法:while b0 do ra%b ab brreturn a欧几里德算法l欧几里德算法是计算最大公约数的传统算法,也是最简单的算法,效率很高l时间复杂度:O(lgn)(最坏情况:斐波那契数列相邻的两项)l空间复杂度:O(1)l但是,对于大整数来说,取模运算非常耗时欧几里德算法l时间复杂度:最坏情况为斐波那契数列相邻的两项体会(13, 8)，(12, 8)a = k*b + c, c = a - k*b同时满足下面两个条件，序列递减得最慢，即辗转相除法的次数最多k =

7、 1最大公约数为1Stein算法l原理: 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算法l例子：两个都为偶数(10, 8) = 2 * (5, 4)一个奇数，一个 偶数(15, 12) = (15, 6)两个都是奇数(25, 15)= (15, 5)Stein算法l Stein算法(假设0=b0 do if a偶,b偶 then aa1 bb1 rr+1 else if a

8、偶,b奇 then aa1 else if a奇,b偶 then bb1 else if a奇,b奇 then a(a-b)1 if ab then 交换a,breturn arStein算法l核心精髓：两个大数的最大公约数转化为两个较小数的最大公约数l时间,空间复杂度均与欧几里德算法相同l最大优点:只有移位和加减法计算,避免了大整数的取模运算第一部分 同余相关 l整除的基本性质l欧几里德算法l扩展欧几里德算法l中国剩余定理扩展欧几里德算法n例子：利用欧几里德算法，求63与81的最大公约数扩展欧几里德算法l原理：对于不完全为 0 的非负整数 a，b，必然存在整数对 x，y，使得 gcd(a，b

9、)=ax+by。a = kb + c, c = a kb在用欧几里德算法求解最大公约数的过程中，将每一步的余数都表示为原始两个数的线性组合形式。最大公约数就是欧几里德算法中，最后不为0的那个余数扩展欧几里德算法l扩展欧几里德算法(递归实现):37扩展欧几里德算法l扩展欧几里德算法(由辗转相除法而来):扩展欧几里德算法l不仅能求得最大公约数，还能求得最大公约数关于原始两个数的线性组合。解二元模线性方程l例子：解方程 15 x + 12 y = 3 5x+4y = 1一组特解：(1, -1)解方程 15x+12y = 65x+4y = 2一组特解：(1, -1)*2解方程15 x + 12 y =

10、 1gcd(15, 12) = 3 ，所以原方程无解解二元模线性方程l二元模线性方程：形如axc(mod b)或ax+by=c其中a,b,c,x,y均为整数原理:令d=gcd(a,b),原方程有整数解当且仅当d|c扩展欧几里德算法解二元模线性方程l解二元模线性方程ax + by = c的一般步骤约分到最简形式，判断该方程是否有解；若有解，则利用扩展欧几里德算法找到初始解利用扩展欧几里德算法求解ax0 + by0 = gcd(a,b);原方程的一组特解（x0，y0）* gcd(a,b)|c加上或者减去两个系数公倍数关于这两个系数的约数，也是这个方程的解第一部分 同余相关 l整除的基本性质l欧几里

11、德算法l扩展欧几里德算法l中国剩余定理中国剩余定理l同模情况下，有这样的性质：乘法原则8 mod 7 = 1加法原则8 mod 7 = 110 mod 7 = 318 mod 7 = 416 mod 7 = 264 mod 7 = 8 mod 7中国剩余定理l在0 14之间找到一个数，使得这个数除以3余1， 除以5余2。经求解该数为7，而且该数唯一。若不限定在0 14之间，那么这样的数为7，22，37，52两个数之间相差3与5的最小公倍数15中国剩余定理l物不知数问题：“今有物不知其数，三三数之剩二；五五数之剩三；七七数之剩二。问物几何?”l物不知数问题的抽象表示:x2(mod 3)x3(mo

12、d 5)x2(mod 7)求满足上述条件的最小正整数x中国剩余定理l物不知数问题的抽象表示: x2(mod 3) x3(mod 5) x2(mod 7) 求满足上述条件的最小正整数xn“物不知数”问题的标准解法:u3k1+1, 5k2, 7k3 （70）u3k1， 5k2+1, 7k3 （21）u3k1， 5k2, 7k3 + 1（15）ux = 70*2+21*3+15*2 = 233ux= 2332*3, 5, 7=23中国剩余定理l一般性问题:给定两两互质的正整数n1,n2,.,nk,要求找到最小的正整数a,满足aai(mod ni)将问题分解成若干次求解二元模线性方程的解二元模线性方程

13、利用扩展欧几里得算法求解。中国剩余定理l算法步骤:令n=n1n2.nk,mi=n/ni利用扩展欧几里德算法计算出xi满足mixi1(mod ni),由于n1,n2,.,nk两两互质,必有gcd(mi,ni)=1,即可保证一定有解则aa1x1m1+a2x2m2+.+akxkmk(mod n)中国剩余定理l典型应用:大整数的表示选取两两互素的正整数n1,n2,.,nk求解对每个ni取模的值ri,这个余数组就可以唯一确定一个1n1n2.nk的大整数l做大整数加,减,乘法时,只要保证在这个范围内,均可转化为分别对相应的余数进行计算数论题目推荐l2342、1528、1953 (都是赤裸裸的)l进阶题目：

14、POJ 1091、POJ 1619、POJ 1845、POJ 2478、POJ 2480、POJ 2603、POJ 2649、POJ 2773、POJ 2992、POJ 329251上节回顾l（12,80）？l（388, 1200）？l（112234, 4556690）？l描述中国剩余定理。52第二部分 素数相关l算术基本定理l筛法（筛法改进）l欧拉定理l素数测试lPollard rho方法53第二部分 素数相关l算术基本定理l筛法（筛法改进）l欧拉定理l素数测试lPollard rho方法54质数（素数）l定义指在一个大于1的自然数中，除了1和自身外，不能被其他自然数整除的数。l合数：比1大

15、但不是素数的数。l1和0既非素数也非合数。l素数与合数是相对的概念。素数，合数，0和1构成了全体自然数。55算术基本定理l任何一个大于1的自然数n,都可以唯一分解成有限个质数的乘积n=p1r1p2r2.pkrkp1p2.=1)，则a与b也互质la1(mod b)，则a与b互质59常见的两数互质情况l两个不同的质数一定是互质数。l一个质数，另一个不为它的倍数，这两个数为互质数。l1和任意自然数都是互质。l相邻的两个自然数是互质数。l相邻的两个奇数是互质数。l较大数是质数的两个数是互质数。60二项式展开定理61筛法l目标:求出n以内的所有质数l算法步骤:初始时容器内为2到n的所有正整数取出容器中最

16、小的数p,p一定是质数,删去p的所有倍数(注:只需从p2开始删除即可)重复上述步骤直到容器为空62筛法63筛法评价l优点:算法简单,空间上只需要一个O(n)的bool数组l缺陷:一个数可能被重复删去多次,影响效率例:在p=2,3,5,7时均会尝试删除210一般的,若x有k个质因子,则x会被处理k次64筛法(改进)l改进:初始时容器内为2到n的所有正整数取出容器中最小的数p,p一定是质数删去所有的pi,令q为第一个未被删除的数,保留q,删去所有的piq,再令q为下一个未被删除的数.直到q遍历所有未被删除的数为止(这一步骤可以把最小质因数为p的所有数删去)重复上面两个步骤直到容器为空65筛法(改进

17、)l用bool数组+双向链表实现,空间复杂度仍为O(n)l小优化:初始时只加入奇数66欧拉函数的前奏l(a, m)=1, (a, n)=1 (a, mn)=1l若(m, n)=1, 则0至mn-1之间的数所有的数用m, n 的余数表法唯一有几个是m的倍数？有几个是n的倍数？有几个既是m的倍数，又是n的倍数？若该数不是m的倍数，则它与m互素吗？67欧拉函数的前奏l若m, n是两个不同的素数, 则0至mn-1之间的数若该数不是m的倍数，则它与m互素吗？有几个数与m互素？有几个数与n互素？既与m互素，又与n互素的数有几个？68例子l若m=3，n=7，则在020之间3的倍数：7的倍数：与3互素的数：与

18、7互素的数：既与3互素，又与7互素的数69欧拉函数l记(x)为与x互质且小于等于x的正整数的个数， (x)就是欧拉函数。70欧拉函数l性质1：若p为素数，(p) = p-1.l性质2：若p为素数，(pk)=pk-1(p-1)l性质3：若(p, q)=1，(pq) = (p) (q) .71欧拉函数l设x=p1r1p2r2.pkrk，则(x)=x*(1-1/p1)*(1-1/p2)*.*(1-1/pk)证明：(piri， pjrj) = 1 (i != j)(x)= (p1r1)* (p2r2)* (pkrk)又(pk)=pk-1(p-1)所以结论得证72欧拉函数l递推形式：设x=p1r1p2r

19、2.pkrk若x中不含素数p，则(px)=(p)*(x)=(p-1) *(x)若x中包含素数p，设第i个质因子为p，则(px)=p*(x)73欧拉函数l扩展:m的所有因子之和(p10+.+p1r1)(p20+.+p2r2).(pk0+.+pkrk)74有关余数的简单性质l对于任意自然数N, 有在0 至N-1之间的数对N取模，所得的余数就是其本身； 任何连续N个自然数对N取模，所得的余数取满了0至N-1之间的每一个数； Eg. N = 10, 连续10个整数：2,3,4,11 余数：2,3,4,5,9,0, 1任何连续N个自然数乘以一个与N互素的数，所得的余数取满了0至N-1之间的每一个数75欧

20、拉定理l欧拉定理：若a和m互质,则a(m)1(mod m)证明:设(m)个正整数r1,r2,.,r(m)满足:ri与m互质,对于任意ij,rirj(mod m)由于a与m互质,可以证明ar1,ar2,.,ar(m) 对m取余依然满足上述条件 这样就有(ar1)(ar2).(ar(m) ) r1r2.r(m)(mod m)而(ar1)(ar2).(ar(m) ) a(m) r1r2.r(m)(mod m)a(m) r1r2.r(m) r1r2.r(m)(mod m)(a(m) -1) r1r2.r(m) 0 (mod m)又r1r2.r(m) 与m互素，所以得到欧拉定理76欧拉定理l利用欧拉定理

21、求下列余数310 mod 5513 mod 11 3200 mod 1777?3200 mod 110578?6200 mod 1079求形如ab mod c 的余数问题 lab mod c 的情形讨论a与c互素；a与c不互素；l方法欧拉定理二进制原理中国剩余定理80求形如ab mod c的余数问题 l513 mod 11 l 6 100 mod 10 l 3200 mod 1105 81求形如ab mod c 的余数问题 l利用二进制原理一般解法（如 513 mod 11 ）目标：将大数的求余转化为较小数的求余步骤：将指数用二进制表示 13 = 20 + 22 + 23 =1 + 4 + 8

22、改写原数 513 = 5 * 54 * 58 研究5i 对11取模的数直到最高位 5 5; 523; 549; 584; (mod 11)513 5*9*44(mod 11)82求形如ab mod c的余数问题 l 利用中国剩余定理的一般解法（如6 100 mod 10 ）令x = 6 100, 又10 = 2 * 5计算x mod 10 等价于求解同余式组x b1(mod 2)x b2(mod 5)找一个最小正整数，使得x满足以下同余式组x 0(mod 2)x 1(mod 5)解得x = 6 就是所求的余数。由欧拉定理计算得到b1=0, b2 = 183l求3200 mod 110584l求

23、6 100 mod 10 85l求2 1000000 mod 77 86不开口算你姓87数论题目推荐l2342、1528、1953 (都是赤裸裸的)l进阶题目：POJ 1091、POJ 1619、POJ 1845、POJ 2478、POJ 2480、POJ 2603、POJ 2649、POJ 2773、POJ 2992、POJ 329288素数测试l费马小定理:若p为素数,则对于任意小于p的正整数a,有a(p-1)1(mod p)l证明:欧拉定理的特例(m为质数)l问题:只是必要条件,不是充分条件(仅对2测试成立)l反例:561,1105,1729.89素数测试l二次探测定理:若p为素数,a2

24、1(mod p)小于p的正整数解只有1和p-1l满足费马小定理和二次探测定理的数可以确定是素数90Miller-Rabin算法lMiller-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进行多次测试91素数测试lMiller-Rabin只能算一种测试,因为通过测试的数不一定是素数,非素数通过测试的概率大约是1/4l虽然一次测试的结果不一定令人满意,但

25、五六次随机测试基本可以保证正确率超过99.9%92大整数分解l至今仍是世界难题l在密码学中起着至关重要的作用l试除法,Fermat方法,Pollard方法lPollard rho方法93Pollard rho方法l原理:设n为待分解的大整数用某种方法生成两个整数a和b,计算p=gcd(a-b,n),直到p不为1或a,b出现循环为止若p=n,则n为质数,否则p为n的一个约数94Pollard rho方法l算法步骤:选取一个小的随机数x1迭代生成xi=x(i-1)2+k,一般取k=1,若序列出现循环则退出计算p=gcd(x(i-1)-xi,n),若p=1,返回上一步继续迭代;否则跳出迭代过程若p=

26、n,则n为素数;否则p为n的一个约数并递归分解p和n/p95Pollard rho方法l可以在(sqrt(p)的期望时间内找出n的一个小因子pl但对于因子很少,因子值很大的大整数n,该方法依然不是很有效96数论小结l前面的这些都是一些初等数论的知识l可以看出,数论所研究的内容,很大一部分都是和素数紧密联系的.因此,数论是名副其实的素论l这些算法代码量都不大,但如果没有准备好模版的话,往往会忽略一些细节进入夏天，少不了一个热字当头，电扇空调陆续登场，每逢此时，总会进入夏天，少不了一个热字当头，电扇空调陆续登场，每逢此时，总会想起那一把蒲扇。蒲扇，是记忆中的农村，夏季经常用的一件物品。记想起那一把

27、蒲扇。蒲扇，是记忆中的农村，夏季经常用的一件物品。记忆中的故乡，每逢进入夏天，集市上最常见的便是蒲扇、凉席，不论男女老忆中的故乡，每逢进入夏天，集市上最常见的便是蒲扇、凉席，不论男女老少，个个手持一把，忽闪忽闪个不停，嘴里叨叨着少，个个手持一把，忽闪忽闪个不停，嘴里叨叨着“怎么这么热怎么这么热”，于是三，于是三五成群，聚在大树下，或站着，或随即坐在石头上，手持那把扇子，边唠嗑五成群，聚在大树下，或站着，或随即坐在石头上，手持那把扇子，边唠嗑边乘凉。孩子们却在周围跑跑跳跳，热得满头大汗，不时听到边乘凉。孩子们却在周围跑跑跳跳，热得满头大汗，不时听到“强子，别跑强子，别跑了，快来我给你扇扇了，快来

28、我给你扇扇”。孩子们才不听这一套，跑个没完，直到累气喘吁吁，。孩子们才不听这一套，跑个没完，直到累气喘吁吁，这才一跑一踮地围过了，这时母亲总是，好似生气的样子，边扇边训，这才一跑一踮地围过了，这时母亲总是，好似生气的样子，边扇边训，“你你看热的，跑什么？看热的，跑什么？”此时这把蒲扇，是那么凉快，那么的温馨幸福，有母亲此时这把蒲扇，是那么凉快，那么的温馨幸福，有母亲的味道！蒲扇是中国传统工艺品，在我国已有三千年多年的历史。取材的味道！蒲扇是中国传统工艺品，在我国已有三千年多年的历史。取材于棕榈树，制作简单，方便携带，且蒲扇的表面光滑，因而，古人常会在上于棕榈树，制作简单，方便携带，且蒲扇的表面光滑，因而，古人常会在上面作画。古有棕扇、葵扇、蒲扇、蕉扇诸名，实即今日的蒲扇，江浙称之为面作画。古有棕扇、葵扇、蒲扇、蕉扇诸名，实即今日的蒲扇，江浙称之为芭蕉扇。六七十年代，人们最常用的就是这种，似圆非圆，轻巧又便宜的蒲芭蕉扇。六七十年代，人们最常用的就是这种，似圆非圆，轻巧又便宜的蒲扇。蒲扇流传至今，我的记忆中，它跨越了半个世纪，也走过了我们的扇。蒲扇流传至今，我的记忆中，它跨越了半个世纪，也走过了我们的半个人生的轨迹，携带着特有的念想，一年年，一天天，流向长长的时间隧半个人生的轨迹，携带着特有的念想，一年年，一天天，流向长长的时间隧道，袅道，袅