ACM中的数学问题March总结.pptx

《ACM中的数学问题March总结.pptx》由会员分享，可在线阅读，更多相关《ACM中的数学问题March总结.pptx（96页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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

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

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

4、页/共96页请写出12，30共有的约数1,2,3,第14页/共96页请写出12，30共有的约数1,2,3,6.第15页/共96页最大公约数与最小公倍数最大公约数定义：两个或若干个整数的公约数中最大的那个公约数例子：12，30的最大公约数如何求两个整数的最大公约数：辗转相除法（扩展版）Stein 算法第16页/共96页请写出12，10共有的倍数第17页/共96页请写出12，10共有的倍数60,第18页/共96页请写出12，10共有的倍数60,120,第19页/共96页请写出12，10共有的倍数60,120,180,第20页/共96页请写出12，10共有的倍数60,120,180,240第21页/

5、共96页最大公约数与最小公倍数最小公倍数定义：两个或若干个整数共有倍数中最小的那一个。例子：12，10的最小公倍数最大公约数与最小公倍数的关系lcm(a,b)*gcd(a,b)=a*b所有的公倍数都是最小公倍数的倍数，所有的公约数都是最大公约数的约数。第22页/共96页欧几里德算法欧几里德算法(The Euclidean Algorithm)又称辗转相除法 或者 短除法原理:gcd(a,b)=gcd(b,a mod b)证明：利用整除性质5(a=kbc=a,b的公因数与b,c的公因数完全相同)辗转相除直到两数整除，其中的除数就是要求的最大公约数。第23页/共96页欧几里德算法例子：利用欧几里德

6、算法，求63与81的最大公约数步骤：a=81,b=63,a mod b=18a 63,b 18,a mod b=9 a 18,b 9,a mod b =0所以9就是63与81的最大公约数第24页/共96页欧几里德算法欧几里德算法:while b0 do ra%b ab brreturn a第25页/共96页欧几里德算法欧几里德算法是计算最大公约数的传统算法,也是最简单的算法,效率很高时间复杂度:O(lgn)(最坏情况:斐波那契数列相邻的两项)空间复杂度:O(1)但是,对于大整数来说,取模运算非常耗时第26页/共96页欧几里德算法时间复杂度:最坏情况为斐波那契数列相邻的两项体会(13,8)，(1

7、2,8)a=k*b+c,c=a-k*b同时满足下面两个条件，序列递减得最慢，即辗转相除法的次数最多k=1最大公约数为1第27页/共96页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)第28页/共96页Stein算法例子：两个都为偶数(10,8)=2*(5,4)一个奇数，一个 偶数(15,12)=(15,6)两个都是奇数(25,15)=(15,5)第29页/共96页Stein算法St

8、ein算法(假设0=b0 do if a偶,b偶 then aa1 bb1 rr+1 else if a偶,b奇 then aa1 else if a奇,b偶 then bb1 else if a奇,b奇 then a(a-b)1 if ab then 交换a,breturn ar第30页/共96页Stein算法核心精髓：两个大数的最大公约数转化为两个较小数的最大公约数时间,空间复杂度均与欧几里德算法相同最大优点:只有移位和加减法计算,避免了大整数的取模运算第31页/共96页第一部分 同余相关 整除的基本性质欧几里德算法扩展欧几里德算法中国剩余定理第32页/共96页扩展欧几里德算法n例子：利用

9、欧几里德算法，求63与81的最大公约数第33页/共96页扩展欧几里德算法原理：对于不完全为 0 的非负整数 a，b，必然存在整数对 x，y，使得 gcd(a，b)=ax+by。a=kb+c,c=a kb在用欧几里德算法求解最大公约数的过程中，将每一步的余数都表示为原始两个数的线性组合形式。最大公约数就是欧几里德算法中，最后不为0的那个余数第34页/共96页扩展欧几里德算法扩展欧几里德算法(递归实现):第35页/共96页扩展欧几里德算法扩展欧几里德算法(由辗转相除法而来):36第36页/共96页扩展欧几里德算法不仅能求得最大公约数，还能求得最大公约数关于原始两个数的线性组合。第37页/共96页解

10、二元模线性方程例子：解方程 15 x+12 y=3 5x+4y=1一组特解：(1,-1)解方程 15x+12y=65x+4y=2一组特解：(1,-1)*2解方程15 x+12 y=1gcd(15,12)=3，所以原方程无解第38页/共96页解二元模线性方程二元模线性方程：形如axc(mod b)或ax+by=c其中a,b,c,x,y均为整数原理:令d=gcd(a,b),原方程有整数解当且仅当d|c扩展欧几里德算法第39页/共96页解二元模线性方程解二元模线性方程ax+by=c的一般步骤约分到最简形式，判断该方程是否有解；若有解，则利用扩展欧几里德算法找到初始解利用扩展欧几里德算法求解ax0+b

11、y0=gcd(a,b);原方程的一组特解（x0，y0）*gcd(a,b)|c加上或者减去两个系数公倍数关于这两个系数的约数，也是这个方程的解第40页/共96页第一部分 同余相关 整除的基本性质欧几里德算法扩展欧几里德算法中国剩余定理第41页/共96页中国剩余定理同模情况下，有这样的性质：乘法原则8 mod 7=1加法原则8 mod 7=110 mod 7=318 mod 7=416 mod 7=264 mod 7=8 mod 7第42页/共96页中国剩余定理在0 14之间找到一个数，使得这个数除以3余1，除以5余2。经求解该数为7，而且该数唯一。若不限定在0 14之间，那么这样的数为7，22，

12、37，52两个数之间相差3与5的最小公倍数15第43页/共96页中国剩余定理物不知数问题：“今有物不知其数，三三数之剩二；五五数之剩三；七七数之剩二。问物几何?”物不知数问题的抽象表示:x2(mod 3)x3(mod 5)x2(mod 7)求满足上述条件的最小正整数x第44页/共96页中国剩余定理物不知数问题的抽象表示: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*

13、3,5,7=23第45页/共96页中国剩余定理一般性问题:给定两两互质的正整数n1,n2,.,nk,要求找到最小的正整数a,满足aai(mod ni)将问题分解成若干次求解二元模线性方程的解二元模线性方程利用扩展欧几里得算法求解。第46页/共96页中国剩余定理算法步骤:令n=n1n2.nk,mi=n/ni利用扩展欧几里德算法计算出xi满足mixi1(mod ni),由于n1,n2,.,nk两两互质,必有gcd(mi,ni)=1,即可保证一定有解则aa1x1m1+a2x2m2+.+akxkmk(mod n)第47页/共96页中国剩余定理典型应用:大整数的表示选取两两互素的正整数n1,n2,.,n

14、k求解对每个ni取模的值ri,这个余数组就可以唯一确定一个1n1n2.nk的大整数做大整数加,减,乘法时,只要保证在这个范围内,均可转化为分别对相应的余数进行计算第48页/共96页数论题目推荐2342、1528、1953(都是赤裸裸的)进阶题目：POJ 1091、POJ 1619、POJ 1845、POJ 2478、POJ 2480、POJ 2603、POJ 2649、POJ 2773、POJ 2992、POJ 3292第49页/共96页上节回顾（12,80）？（388,1200）？（112234,4556690）？描述中国剩余定理。50第50页/共96页第二部分 素数相关算术基本定理筛法（筛

15、法改进）欧拉定理素数测试Pollard rho方法51第51页/共96页第二部分 素数相关算术基本定理筛法（筛法改进）欧拉定理素数测试Pollard rho方法52第52页/共96页质数（素数）定义指在一个大于1的自然数中，除了1和自身外，不能被其他自然数整除的数。合数：比1大但不是素数的数。1和0既非素数也非合数。素数与合数是相对的概念。素数，合数，0和1构成了全体自然数。53第53页/共96页算术基本定理任何一个大于1的自然数n,都可以唯一分解成有限个质数的乘积n=p1r1p2r2.pkrkp1p2.=1)，则a与b也互质a1(mod b)，则a与b互质57第57页/共96页常见的两数互质

16、情况两个不同的质数一定是互质数。一个质数，另一个不为它的倍数，这两个数为互质数。1和任意自然数都是互质。相邻的两个自然数是互质数。相邻的两个奇数是互质数。较大数是质数的两个数是互质数。58第58页/共96页筛法目标:求出n以内的所有质数算法步骤:初始时容器内为2到n的所有正整数取出容器中最小的数p,p一定是质数,删去p的所有倍数(注:只需从p2开始删除即可)重复上述步骤直到容器为空60第60页/共96页筛法61第61页/共96页筛法评价优点:算法简单,空间上只需要一个O(n)的bool数组缺陷:一个数可能被重复删去多次,影响效率例:在p=2,3,5,7时均会尝试删除210一般的,若x有k个质因

17、子,则x会被处理k次62第62页/共96页筛法(改进)改进:初始时容器内为2到n的所有正整数取出容器中最小的数p,p一定是质数删去所有的pi,令q为第一个未被删除的数,保留q,删去所有的piq,再令q为下一个未被删除的数.直到q遍历所有未被删除的数为止(这一步骤可以把最小质因数为p的所有数删去)重复上面两个步骤直到容器为空63第63页/共96页筛法(改进)用bool数组+双向链表实现,空间复杂度仍为O(n)小优化:初始时只加入奇数64第64页/共96页欧拉函数的前奏(a,m)=1,(a,n)=1 (a,mn)=1若(m,n)=1,则0至mn-1之间的数所有的数用m,n 的余数表法唯一有几个是m

18、的倍数？有几个是n的倍数？有几个既是m的倍数，又是n的倍数？若该数不是m的倍数，则它与m互素吗？65第65页/共96页欧拉函数的前奏若m,n是两个不同的素数,则0至mn-1之间的数若该数不是m的倍数，则它与m互素吗？有几个数与m互素？有几个数与n互素？既与m互素，又与n互素的数有几个？66第66页/共96页例子若m=3，n=7，则在020之间3的倍数：7的倍数：与3互素的数：与7互素的数：既与3互素，又与7互素的数67第67页/共96页欧拉函数记(x)为与x互质且小于等于x的正整数的个数，(x)就是欧拉函数。68第68页/共96页欧拉函数性质1：若p为素数，(p)=p-1.性质2：若p为素数，

19、(pk)=pk-1(p-1)性质3：若(p,q)=1，(pq)=(p)(q).69第69页/共96页欧拉函数设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)所以结论得证70第70页/共96页欧拉函数递推形式：设x=p1r1p2r2.pkrk若x中不含素数p，则(px)=(p)*(x)=(p-1)*(x)若x中包含素数p，设第i个质因子为p，则(px)=p*(x)71第71页/共96页欧拉函数扩展:m的所有因子之和(p1

20、0+.+p1r1)(p20+.+p2r2).(pk0+.+pkrk)72第72页/共96页有关余数的简单性质对于任意自然数N,有1.在0 至N-1之间的数对N取模，所得的余数就是其本身；2.任何连续N个自然数对N取模，所得的余数取满了0至N-1之间的每一个数；Eg.N=10,连续10个整数：2,3,4,11余数：2,3,4,5,9,0,13.任何连续N个自然数乘以一个与N互素的数，所得的余数取满了0至N-1之间的每一个数73第73页/共96页欧拉定理欧拉定理：若a和m互质,则a(m)1(mod m)证明:设(m)个正整数r1,r2,.,r(m)满足:ri与m互质,对于任意ij,rirj(mod

21、 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互素，所以得到欧拉定理74第74页/共96页欧拉定理利用欧拉定理求下列余数310 mod 5513 mod 11 3200 mod 1775第75页/共96页?3200 mod 110576第76页/共96页?6200 mod 10

22、77第77页/共96页求形如ab mod c 的余数问题 ab mod c 的情形讨论a与c互素；a与c不互素；方法欧拉定理二进制原理中国剩余定理78第78页/共96页求形如ab mod c的余数问题 513 mod 11 l6 100 mod 10 l3200 mod 1105 79第79页/共96页求形如ab mod c 的余数问题 利用二进制原理一般解法（如 513 mod 11）目标：将大数的求余转化为较小数的求余步骤：将指数用二进制表示13=20+22+23=1+4+8改写原数 513=5*54*58 研究5i 对11取模的数直到最高位5 5;523;549;584;(mod 11)

23、513 5*9*44(mod 11)80第80页/共96页求形如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 就是所求的余数。81由欧拉定理计算得到b1=0,b2=1第81页/共96页求3200 mod 110582第82页/共96页求6 100 mod 10 83第83页/共96页求2 1000000 mod 77 84第84页/共96页不开口算你姓85第85页/共96页数论题目推荐2342、1528、1953(都是赤裸裸的)进阶题目：POJ 1091、POJ 1619、POJ 1845、POJ 2478、POJ 2480、POJ 2603、POJ 2649、POJ 2773、POJ 2992、POJ 329286第86页/共96页96谢谢大家观赏！第96页/共96页