《ACM中的数学问题数论部分.ppt》由会员分享，可在线阅读，更多相关《ACM中的数学问题数论部分.ppt（70页珍藏版）》请在三一办公上搜索。
1、ACM中的数学问题,第一部分：数论,主讲人：钱明日期：Dec 05,2012,引言,在ACM竞赛中,经常可以看到数学问题的身影可以是纯数学问题,也可以是需要利用数学上的一些公式,定理,算法来辅助解决的问题会者不难,而不会的选手在赛场上一般很难推出公式或进行证明往往想起来费劲,写起来却很轻松,常见的数学问题,数论组合数学计算几何博弈论线性代数高等数学线性规划概率统计.,本讲内容,基本上是最基础的,同时也是ACM竞赛中最常见的数学问题对一些数学公式,定理进行简略地推导或证明,从而加深对它们的理解和认识,也方便记忆往届ACM竞赛中的数学问题,数论,简而言之,数论就是研究整数的理论在ACM竞赛中,经常
2、用到与数论相关的知识纯数论的题目不多,大部分是和其他类型的问题结合起来的,数论的历史,自古以来,许许多多的数学家研究过与数论有关的问题直到十九世纪,数论才真正形成了一门独立的学科数论是一门高度抽象的学科,长期处于纯理论研究的状态,曾经被认为是很难有应用价值的随着计算机科学的发展,数论得到了广泛的应用,数论主要内容,第一部分:同余相关整除的性质欧几里德算法扩展欧几里德算法中国剩余定理第二部分:素数相关算术基本定理欧拉定理素数测试Pollard rho方法,数论主要内容,第一部分:同余相关整除的性质欧几里德算法扩展欧几里德算法中国剩余定理第二部分:素数相关算术基本定理欧拉定理素数测试Pollard
3、 rho方法,第一部分 同余相关,整除的基本性质欧几里德算法扩展欧几里德算法中国剩余定理,整除的符号,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的
4、公因数，也能证出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
5、,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的公因数完全相同)辗转相除直到两数整除，其中的除数就是要求的最大公约数。,
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的最大公约数,欧几里德算法,欧几里德算法:while b0 do ra%b ab brreturn a,欧几里德算法,欧几里德算法是计算最大公约数的传统算法,也是最简单的算法,效率很高时间复杂度:O(lgn)(最坏情况:斐波那契数列相邻的两项)空间复杂度:O(1)但是,对于大整数来说,取模运算非常耗时,欧几里德算法,时间复杂度:最坏情况为斐波那契数列相邻的两项体会(13,8)，(12,8)a=
7、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算法(假设00 do if a偶,b偶 then
8、 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,Stein算法,核心精髓：两个大数的最大公约数转化为两个较小数的最大公约数时间,空间复杂度均与欧几里德算法相同最大优点:只有移位和加减法计算,避免了大整数的取模运算,第一部分 同余相关,整除的基本性质欧几里德算法扩展欧几里德算法中国剩余定理,扩展欧几里德算法,例子：利用欧几里德算法，求63与81的最大公约数,扩展欧几里德算法,原理：对于不完全为 0 的非负整数 a，b，必
9、然存在整数对 x，y，使得 gcd(a，b)=ax+by。a=kb+c,c=a kb在用欧几里德算法求解最大公约数的过程中，将每一步的余数都表示为原始两个数的线性组合形式。最大公约数就是欧几里德算法中，最后不为0的那个余数,扩展欧几里德算法,扩展欧几里德算法(递归实现):int gcd(int a,int b)if b=0 then x1 y0 return a dgcd(b,a%b)xy yx-a/by xx yy return d,扩展欧几里德算法,不仅能求得最大公约数，还能求得关于原始两个数的线性组合。,解二元模线性方程,例子：解方程 15 x+12 y=3 5x+4y=1(1,-1)解
10、方程 15x+12y=65x+4y=2(1,-1)*2解方程15 x+12 y=1gcd(15,12)=3，所以原方程无解,解二元模线性方程,二元模线性方程：形如axc(mod b)或ax+by=c其中a,b,c,x,y均为整数原理:令d=gcd(a,b),原方程有整数解当且仅当d|c扩展欧几里德算法,解二元模线性方程,解二元模线性方程的一般步骤约分到最简形式找到初始解（扩展欧几里德算法）加上或者减去两个系数最小公倍数关于这两个系数的约数，也是这个方程的解,第一部分 同余相关,整除的基本性质欧几里德算法扩展欧几里德算法中国剩余定理,中国剩余定理,同模情况下，有这样的性质：乘法原则8 mod 7
11、=1加法原则8 mod 7=110 mod 7=3,18 mod 7=4,16 mod 7=264 mod 7=8 mod 7,中国剩余定理,在0 14之间找到一个数，使得这个数除以3余1，除以5余2。经求解该数为7，而且该数唯一。若不限定在0 14之间，那么这样的数为7，22，37，52两个数之间相差3与5的最小公倍数15,中国剩余定理,物不知数问题的抽象表示:x2(mod 3)x3(mod 5)x2(mod 7)求满足上述条件的最小正整数x,中国剩余定理,物不知数问题的抽象表示:x2(mod 3)x3(mod 5)x2(mod 7)求满足上述条件的最小正整数x,“物不知数”问题的标准解法:
12、3k1+1,5k2,7k3（70）3k1，5k2+1,7k3（21）3k1，5k2,7k3+1（15）x=70*2+21*3+15*2=233x=2332*3,5,7=23,中国剩余定理,一般性问题:给定两两互质的正整数n1,n2,.,nk,要求找到最小的正整数a,满足aai(mod ni)将问题分解成若干次求解二元模线性方程组的解用扩展欧几里德算法求解二元模线性方程,中国剩余定理,算法步骤:令n=n1n2.nk,mi=n/ni利用扩展欧几里德算法计算出xi满足mixi1(mod ni),由于n1,n2,.,nk两两互质,必有gcd(mi,ni)=1,即可保证一定有解则aa1x1m1+a2x2
13、m2+.+akxkmk(mod n),中国剩余定理,典型应用:大整数的表示选取两两互素的正整数n1,n2,.,nk求解对每个ni取模的值ri,这个余数组就可以唯一确定一个1n1n2.nk的大整数做大整数加,减,乘法时,只要保证在这个范围内,均可转化为分别对相应的余数进行计算,数论题目推荐,2342、1528、1953(都是赤裸裸的)进阶题目：POJ 1091、POJ 1619、POJ 1845、POJ 2478、POJ 2480、POJ 2603、POJ 2649、POJ 2773、POJ 2992、POJ 3292,第二部分 素数相关,算术基本定理欧拉定理素数测试Pollard rho方法,
14、关于互素的性质,a与b,c同时互素，则a与b*c也互素p为素数，p|b*cp|b or p|ca*b|c and(a,c)=1b|cak与b互素(k=1)，则a与b也互素a1(mod b)，则a与b互素,筛法,目标:求出n以内的所有质数算法步骤:初始时容器内为2到n的所有正整数取出容器中最小的数p,p一定是质数,删去p的所有倍数(注:只需从p2开始删除即可)重复上述步骤直到容器为空,筛法,优点:算法简单,空间上只需要一个O(n)的bool数组缺陷:一个数可能被重复删去多次,影响效率例:在p=2,3,5,7时均会尝试删除210一般的,若x有k个质因子,则x会被处理k次,筛法(改进),改进:初始时
15、容器内为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
16、*(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(mod m)证明:设(m)个正整数r1,r2,.,r(m)满足:ri与m互质,
17、对于任意ij,rirj(mod m)由于a与m互质,可以证明ar1,ar2,.,ar(m)依然满足上述条件这样就有(ar1)(ar2).(ar(m)r1r2.r(m)(mod m)而(ar1)(ar2).(ar(m)a(m)r1r2.r(m)(mod m)两边同时约去r1r2.r(m)即得到欧拉定理,素数测试,费马小定理:若p为素数,则对于任意小于p的正整数a,有a(p-1)1(mod p)证明:欧拉定理的特例(m为质数)问题:只是必要条件,不是充分条件反例:561,1105,1729.,素数测试,二次探测定理:若p为素数,a21(mod p)小于p的正整数解只有1和p-1满足费马小定理和二次
18、探测定理的数可以确定是素数,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%,大整数分解,至今仍是世界难
19、题在密码学中起着至关重要的作用试除法,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方法,算法步骤:选取一个小的随机数x1迭代生成xi=x(i-1)2+k,一般取k=1,若序列出现循环则退出计算p=gcd(x(i-1)-xi,n),若p=1,返回上一步继续迭代;否则跳出迭代过程若p=n,则n为素数;否则p为n的一个约数并递归分解p和n/p,Pollard rho方法,可以在(sqrt(p)的期望时间内找出n的一个小因子p但对于因子很少,因子值很大的大整数n,该方法依然不是很有效,数论小结,前面的这些都是一些初等数论的知识可以看出,数论所研究的内容,很大一部分都是和素数紧密联系的.因此,数论是名副其实的素论这些算法代码量都不大,但如果没有准备好模版的话,往往会忽略一些细节,
