ACM中的数学问题-March+10-2013总结

1、ACM中的数学问题第一部分：数论主讲人：陈双敏日期：Dec 21, 20121本讲内容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小整除的基

3、本性质l性质1：a|b,b|c = a|cl性质2 ：a|b = a|bcl性质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

4、，30共有的约数1, 2, 请写出12，30共有的约数1, 2, 3,请写出12，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

5、最小公倍数定义：两个或若干个整数共有倍数中最小的那一个。例子：12，10的最小公倍数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

6、= 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的最大公约数欧几里德算法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 -

7、 k*b同时满足下面两个条件，序列递减得最慢，即辗转相除法的次数最多k = 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

8、 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 arStein算法l核心精髓：两个大数的最大公约数转化为两个较小数的最大公约数l时间,空间复杂度均与欧几里德算法相同l最大优点:只有移位和加减法计算,避免了大整数的取模运算第一部分 同余相关 l整除的基本性质l欧几里德算法l扩展欧几里德算法l中国剩余定理扩展欧几里德算法n例子：利用欧几里德算法，求63与81的最大公约数扩展欧几里德算法l原理：对于不完

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

10、+4y = 2一组特解：(1, -1)*2解方程15 x + 12 y = 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加上或者减去两个系数公倍数关于这两

11、个系数的约数，也是这个方程的解第一部分 同余相关 l整除的基本性质l欧几里德算法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物不知数问题：“今有物不知其数，三三数之剩二；五五数之剩三；七七数

12、之剩二。问物几何?”l物不知数问题的抽象表示:x2(mod 3)x3(mod 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,满足a

13、ai(mod ni)将问题分解成若干次求解二元模线性方程的解二元模线性方程利用扩展欧几里得算法求解。中国剩余定理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做大整数加,减,乘法时,只要保证在这个范围内,均可转化为分别对相应的余数进行计

14、算数论题目推荐l2342、1528、1953 (都是赤裸裸的)l进阶题目：POJ 1091、POJ 1619、POJ 1845、POJ 2478、POJ 2480、POJ 2603、POJ 2649、POJ 2773、POJ 2992、POJ 3292上节回顾l（12,80）？l（388, 1200）？l（112234, 4556690）？l描述中国剩余定理。51第二部分 素数相关l算术基本定理l筛法（筛法改进）l欧拉定理l素数测试lPollard rho方法52第二部分 素数相关l算术基本定理l筛法（筛法改进）l欧拉定理l素数测试lPollard rho方法53质数（素数）l定义指在一个大于

15、1的自然数中，除了1和自身外，不能被其他自然数整除的数。l合数：比1大但不是素数的数。l1和0既非素数也非合数。l素数与合数是相对的概念。素数，合数，0和1构成了全体自然数。54算术基本定理l任何一个大于1的自然数n,都可以唯一分解成有限个质数的乘积n=p1r1p2r2.pkrkp1p2.=1)，则a与b也互质la1(mod b)，则a与b互质58常见的两数互质情况l两个不同的质数一定是互质数。l一个质数，另一个不为它的倍数，这两个数为互质数。l1和任意自然数都是互质。l相邻的两个自然数是互质数。l相邻的两个奇数是互质数。l较大数是质数的两个数是互质数。59二项式展开定理60筛法l目标:求出n

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

17、最小质因数为p的所有数删去)重复上面两个步骤直到容器为空64筛法(改进)l用bool数组+双向链表实现,空间复杂度仍为O(n)l小优化:初始时只加入奇数65欧拉函数的前奏l(a, m)=1, (a, n)=1 (a, mn)=1l若(m, n)=1, 则0至mn-1之间的数所有的数用m, n 的余数表法唯一有几个是m的倍数？有几个是n的倍数？有几个既是m的倍数，又是n的倍数？若该数不是m的倍数，则它与m互素吗？66欧拉函数的前奏l若m, n是两个不同的素数, 则0至mn-1之间的数若该数不是m的倍数，则它与m互素吗？有几个数与m互素？有几个数与n互素？既与m互素，又与n互素的数有几个？67例子

18、l若m=3，n=7，则在020之间3的倍数：7的倍数：与3互素的数：与7互素的数：既与3互素，又与7互素的数68欧拉函数l记(x)为与x互质且小于等于x的正整数的个数， (x)就是欧拉函数。69欧拉函数l性质1：若p为素数，(p) = p-1.l性质2：若p为素数，(pk)=pk-1(p-1)l性质3：若(p, q)=1，(pq) = (p) (q) .70欧拉函数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

19、-1(p-1)所以结论得证71欧拉函数l递推形式：设x=p1r1p2r2.pkrk若x中不含素数p，则(px)=(p)*(x)=(p-1) *(x)若x中包含素数p，设第i个质因子为p，则(px)=p*(x)72欧拉函数l扩展:m的所有因子之和(p10+.+p1r1)(p20+.+p2r2).(pk0+.+pkrk)73有关余数的简单性质l对于任意自然数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.

20、 任何连续N个自然数乘以一个与N互素的数，所得的余数取满了0至N-1之间的每一个数74欧拉定理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

21、(mod m)又r1r2.r(m) 与m互素，所以得到欧拉定理75欧拉定理l利用欧拉定理求下列余数310 mod 5513 mod 11 3200 mod 1776?3200 mod 110577?6200 mod 1078求形如ab mod c 的余数问题 lab mod c 的情形讨论a与c互素；a与c不互素；l方法欧拉定理二进制原理中国剩余定理79求形如ab mod c的余数问题 l513 mod 11 l 6 100 mod 10 l 3200 mod 1105 80求形如ab mod c 的余数问题 l利用二进制原理一般解法（如 513 mod 11 ）目标：将大数的求余转化为较小数

22、的求余步骤：将指数用二进制表示 13 = 20 + 22 + 23 =1 + 4 + 8改写原数 513 = 5 * 54 * 58 研究5i 对11取模的数直到最高位 5 5; 523; 549; 584; (mod 11)513 5*9*44(mod 11)81求形如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 就是所求的余

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