ACM中的数学问题--课件

ACMACM中的数学问题中的数学问题中的数学问题中的数学问题1ppt课件引言在ACM竞赛中,经常可以看到数学问题的身影可以是纯数学问题,也可以是需要利用数学上的一些公式,定理,算法来辅助解决的问题会者不难,而不会的选手在赛场上一般很难推出公式或进行证明往往想起来费劲,写起来却很轻松2ppt课件常见的数学问题数论组合数学博弈论线性代数高等数学线性规划概率统计.3ppt课件本讲内容简单数论Polya定理SG函数与矩阵有关的问题4ppt课件本讲内容基本上是最基础的,同时也是ACM竞赛中最常见的数学问题对一些数学公式,定理进行简略地推导或证明,从而加深对它们的理解和认识,也方便记忆往届ACM竞赛中的数学问题5ppt课件数论简而言之,数论就是研究整数的理论在ACM竞赛中,经常用到数论的相关知识纯数论的题目不多,大部分是和其他类型的问题结合起来的约数,倍数,模线性方程,欧拉定理,素数6ppt课件数论的历史自古以来,许许多多的数学家研究过与数论有关的问题直到十九世纪,数论才真正形成了一门独立的学科数论是一门高度抽象的学科,长期处于纯理论研究的状态,曾经被认为是很难有应用价值的随着计算机科学的发展,数论得到了广泛的应用7ppt课件数论主要内容第一部分:同余相关整除的性质-欧几里德算法-扩展欧几里德算法-中国剩余定理第二部分:素数相关算术基本定理-欧拉定理-素数测试-Pollard rho方法8ppt课件第一部分 同余相关 整除的性质欧几里德算法扩展欧几里德算法中国剩余定理9ppt课件整除的性质性质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的公因数完全相同10ppt课件整除的性质性质5 a=kbc=a,b的公因数与b,c的公因数完全相同利用性质3(a|b,a|c=a|kblc)证明:对于任意的a,b的公因数da=kbc=c=(a-kb)=d|c11ppt课件最大公约数 最小公倍数求最大公约数:欧几里德算法(辗转相除法,短除法)原理:若ar(mod b),则gcd(a,b)=gcd(b,r)可利用性质5(a=kbc=a,b的公因数与b,c的公因数完全相同)证明最小公倍数:lcm(a,b)=a*b/gcd(a,b)12ppt课件欧几里德算法欧几里德算法:while b0 do ra%b ab brreturn a13ppt课件欧几里德算法欧几里德算法是计算最大公约数的传统算法,也是最简单的算法,效率很高时间复杂度:O(lgn)(最坏情况:斐波那契数列相邻的两项)空间复杂度:O(1)但是,对于大整数来说,取模运算非常耗时14ppt课件Stein算法另一种算法:Stein算法渐近时间,空间复杂度均与欧几里德算法相同原理:gcd(ka,kb)=k*gcd(a,b)最大特点:只有移位和加减法计算,避免了大整数的取模运算15ppt课件Stein算法Stein算法(假设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 ar16ppt课件解二元模线性方程二元模线性方程(二元一次不定方程):形如axc(mod b)或ax+by=c其中a,b,c,x,y均为整数扩展欧几里德算法原理:令d=gcd(a,b),原方程有整数解当且仅当d|cbx+(a%b)y=1 ay+b(x-a/b*y)=117ppt课件扩展欧几里德算法具体方法:在用欧几里德算法求d=gcd(a,b)的过程中求方程ax+by=d的一组整数解(x,y)若d|c,不妨设c=kd,则有a(kx)+b(ky)=c;否则原方程无整数解18ppt课件扩展欧几里德算法扩展欧几里德算法(递归实现):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 d19ppt课件中国剩余定理孙子定理,韩信点兵,隔墙算,鬼谷算,大衍求一术.物不知数问题:今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?答曰:二十三.术曰:三三数之剩二,置一百四十,五五数之剩三,置六十三,七七数之剩二,置三十,并之,得二百三十三,以二百一十减之,即得.凡三三数之剩一,则置七十,五五数之剩一,则置二十一,七七数之剩一,则置十五,即得.-孙子算经20ppt课件中国剩余定理物不知数问题的抽象表示:x2(mod 3)x3(mod 5)x2(mod 7)求满足上述条件的最小正整数x21ppt课件中国剩余定理物不知数解法的数学表示:任取被3除余2的5和7的倍数:140任取被5除余3的7和3的倍数:63任取被7除余2的3和5的倍数:30140+63+30=233减去3,5,7的公倍数中不超过233的最大的数210得到答案2322ppt课件中国剩余定理一般性问题:给定两两互质的正整数n1,n2,.,nk,要求找到最小的正整数a,满足aai(mod ni)将问题分解成若干次求解二元模线性方程组的解23ppt课件中国剩余定理算法步骤:令n=n1n2.nk,mi=n/ni利用扩展欧几里德算法计算出xi满足mixi1(mod ni),由于n1,n2,.,nk两两互质,必有gcd(mi,ni)=1,即可保证一定有解则aa1x1m1+a2x2m2+.+akxkmk(mod n)24ppt课件中国剩余定理典型应用:大整数的表示选取两两互素的正整数n1,n2,.,nk已知对每个ni取模的值ri,就可以唯一确定一个1n1n2.nk的大整数做大整数加,减,乘法时,只要保证在这个范围内,均可转化为分别对相应的余数进行计算25ppt课件第二部分 素数相关算术基本定理欧拉定理素数测试Pollard rho方法26ppt课件筛法目标:求出n以内的所有质数算法步骤:初始时容器内为2到n的所有正整数取出容器中最小的数p,p一定是质数,删去p的所有倍数(注:只需从p2开始删除即可)重复上述步骤直到容器为空27ppt课件筛法优点:算法简单,空间上只需要一个O(n)的bool数组缺陷:一个数可能被重复删去多次,影响效率例:在p=2,3,5,7时均会尝试删除210一般的,若x有k个质因子,则x会被处理k次28ppt课件筛法(改进)改进:初始时容器内为2到n的所有正整数取出容器中最小的数p,p一定是质数删去所有的pi,令q为第一个未被删除的数,保留q,删去所有的piq,再令q为下一个未被删除的数.直到q遍历所有未被删除的数为止(这一步骤可以把最小质因数为p的所有数删去)重复上面两个步骤直到容器为空29ppt课件筛法(改进)用bool数组+双向链表实现,空间复杂度仍为O(n)小优化:初始时只加入奇数30ppt课件算术基本定理任何一个大于1的自然数n,都可以唯一分解成有限个质数的乘积n=p1r1p2r2.pkrkp1p2.x2,x2-x3,.,xn-x1,这样x1,x2,.,xn就构成了一个轮换,记为(x1 x2.xn)定义ck为置换ak中的轮换个数例子中:c1=6,c2=1,c3=2,c4=3,c5=2,c6=148ppt课件Polya定理设G=a1,a2,.,a|G|是N=1,2,.,N上的置换群,现用m种颜色对这N个点染色,则不同的染色方案数为S=(mc1+mc2+.+mc|G|)/|G|证明比较复杂,略49ppt课件利用Polya定理解决组合计数问题的步骤写出置换群123456 123456 123456123456 612345 561234123456 123456 123456456123 345612 234561求出每个置换的轮换个数 c1=6,c2=1,c3=2,c4=3,c5=2,c6=1计算染色方案S=(26+21+22+23+22+21)/6=1450ppt课件常见置换的轮换个数计算置换的轮换个数,是这一算法的瓶颈.如果能够根据问题的特殊性快速计算出各置换的轮换个数,就可以大大提高程序的运行效率旋转:n个点顺时针(或逆时针)旋转i个位置的置换,轮换个数为gcd(n,i)翻转:n为偶数且对称轴不过顶点:轮换个数为n/2n为偶数且对称轴过顶点:轮换个数为n/2+1n为奇数:轮换个数为(n+1)/251ppt课件Polya定理小结前面所讲的内容,仅适用于置换数目较少,着色没有其他限制的情况,是最简单的一类Polya定理的问题复杂的Polya定理的问题还需要用到数论知识来加快速度,用排列组合或动态规划来辅助计数不过,对于ACM竞赛来说,掌握简单的Polya定理就能够解决很多问题了52ppt课件从博弈说起一种古老的游戏;棋牌,彩票.博弈论是二人或多人在对局中,各自利用对方的策略,变换自己的对抗策略,达到取胜目标的理论合作博弈/非合作博弈静态博弈/动态博弈完全信息博弈/非完全信息博弈53ppt课件公平组合博弈二人博弈非合作博弈:博弈双方利益完全对立动态博弈:两人轮流行动,后手知道先手的动作完全信息博弈:双方都了解当前格局非偶然性:无随机事件54ppt课件公平组合博弈游戏局面的状态数有限且总能在有限步内结束对于同一局面,两个游戏者可操作的集合完全相同无法进行任何操作时游戏结束,不能操作的一方为负游戏总可以在有限步之内结束假定:两个人都足够聪明55ppt课件先手必胜/后手必胜由于公平组合博弈必在有限步结束,且不会有随机事件,因此,在双方都采用最佳策略的前提下,任一局面不是先手必胜就是后手必胜规定:先手胜为N(Next)局面,后手胜为P(Pre)局面56ppt课件先手必胜/后手必胜最终局面都是P局面对于一个局面,若至少有一种操作使它变为P局面,则它是N局面对于一个局面,无论如何操作都使它变为N局面,则它是P局面57ppt课件抽象模型所有的公平组合博弈都可以抽象成下列模型:有向无环图,某个点上有一枚棋子,双方轮流将棋子沿有向边移动一步,无法移动者为负其中,一个点表示一个局面,而一条有向边则表示一种可行操作58ppt课件公平组合博弈问题解法往往可以从终局面出发,逆向递推,求出任意局面是P局面还是N局面但如果游戏是一系列子游戏的组合时,局面的数量非常庞大,上述方法就会变得十分低效下面将引入SG函数来解决这一类问题59ppt课件mex函数定义函数mex,表示取最小的不属于该集合的非负整数例:mex=0mex0,1,2,4=3mex2,3=060ppt课件SG函数定义有向图每个顶点的SG函数值g(x)=mexg(y)|y是x的后继若g(x)=0,则x为P局面若g(x)0,则x为N局面简略证明:终局面g(x)=0若g(x)0,则至少有一个后继y满足g(y)=0若g(x)=0,则任何后继y都有g(y)061ppt课件游戏的和设G1,G2,.,Gn是n个公平组合博弈游戏定义G为G1,G2,.,Gn的和:G的移动规则为任选一个子游戏Gi操作一次则G的SG函数值g(G)=g(G1)g(G2).g(Gn)注:为异或符号62ppt课件游戏的和若g(G)=0,则游戏G后手必胜若g(G)0,则游戏G先手必胜证明思路:证明下列三条即可终局面SG函数值为0若SG函数值不为0,则一定存在一个操作使得新局面的SG函数值为0若SG函数值为0,则任何操作都会使新局面的SG值大于063ppt课件SG函数小结有了SG函数这一工具,我们可以把这一类复杂的游戏分解成若干个简单的子游戏,然后依次求出每个子游戏的SG函数值,最后异或起来,就可以判断原游戏先手胜还是后手胜的问题了64ppt课件ACM中的矩阵在ACM竞赛中,有时会碰到一些与矩阵有关的问题高斯消元矩阵分解转移矩阵,矩阵乘法施密特正交化特征值,特征向量相似,合同.65ppt课件ACM中的矩阵在线性代数的课程中基本上都已经学过这些问题虽然在线性代数中都有标准的一般解法,但有的解法仍停留在理论上,实际上不易利用计算机来解决ACM竞赛不会考很难的线性代数问题下面只介绍一些简单的算法66ppt课件高斯消元将系数和常数项写成增广矩阵的形式利用初等行变换将增广矩阵转化为阶梯型矩阵若某一行系数全为0而常数不为0,原方程组无解,退出;若出现全零的列,则原方程组有无穷多个解,全零列对应的变量为自由变量;否则原方程组只有唯一解利用初等行变换将阶梯型矩阵转化为简化阶梯型矩阵从下到上依次求出每个变量的值67ppt课件高斯消元注意事项:在将增广矩阵转化为阶梯型矩阵的过程中,最好取该列绝对值最大的元素作为主元,因为若绝对值较小,将其化成1需要乘以一个绝对值较大系数,这样会将误差放大在有无穷多解的情况下,若要求出一个可行解,只需对每个自由变量赋任意值(一般取0,1之类的数),然后解出每个主变量即可68ppt课件施密特正交化给定某空间的一组基1,2,.,s,求该空间的一组正交基1,2,.,s施密特正交化:1=12=2-(2,1)/(1,1)1.s=s-(s,1)/(1,1)1-(s,2)/(2,2)2-.-(s,s-1)/(s-1,s-1)s-169ppt课件矩阵分解任意矩阵A可以做下列几种形式的分解A=PJ,P是可逆矩阵,J是简化阶梯型矩阵(高斯消元)A=QR,Q是正交矩阵(QQ=I),R是上三角矩阵(施密特正交化)A=PU,P是投影矩阵(P2=P),U是可逆矩阵A=PQ,P是对称矩阵(P=P),Q是正交矩阵70ppt课件矩阵小结ACM竞赛中有关矩阵的问题大多数是高斯消元和矩阵乘法但矩阵的一些基本问题的解法还是应该有所了解,这些有利于熟练地利用矩阵理论来思考问题,解决问题71ppt课件总结要解决ACM中的数学问题,关键还是要有扎实的数学基础和灵活的数学思维但ACM竞赛并不是数学竞赛,一味地钻研理论是没有任何意义的,更重要的是如何利用数学知识来解决实际生活中的问题ACM中的数学问题涵盖了很多内容,因此,数学的各个方向都需要有一定的了解72ppt课件AstronomyPOJ3101题目大意:有n个行星,它们的轨道是同一平面上的同向同心圆,且它们始终做匀速圆周运动,周期ti已知所有卫星都处于过圆心的某条直线上的现象,称为卫星平行求相邻两次卫星平行现象的间隔时间,用分数表示73ppt课件Astronomy算法思路:所有卫星平行任意两个卫星平行相邻两个卫星平行(卫星平行具有传递性)两个卫星i,j平行的时间间隔为|0.5/(1/ti-1/tj)|(追及问题,注意是相差半周,而不是相差整周)写出相邻两个卫星平行的时间间隔di=bi/ai,则问题转化为求这n-1个分数的最小公倍数分母p=gcd(a1,a2,.,an-1),分子q=lcm(b1,b2,.,bn-1),约分即得最终答案74ppt课件The Balance POJ2142题目大意:现有质量为a和b的砝码,数量不限要求在天平上称出质量为d的物品,天平左右均可放砝码求一种可行方案,要求:放置砝码数量尽可能少;数量相同时,总质量尽可能少75ppt课件The Balance算法思路:问题转化:求ax+by=d的一组整数解(x,y),要求|x|+|y|尽可能小,若相等,则a|x|+b|y|尽可能小(x0,t为整数)不妨设ab,可以证明,当|x|+|y|最小时,一定会有-ay筛法+试除先用筛法求出不大于sqrt(U)的所有素数,然后用这些素数一一试除80ppt课件Farey SequencePOJ2478题目大意:求所有分母不大于n的既约真分数个数81ppt课件Farey Sequence算法思路:分母为x的既约真分数有(x)个分母不大于n的既约真分数个数为(1)+(2)+.+(n)还记得递推式吗?递推式:质数p满足p|x,若p2|x,则(x)=(x/p)*p,否则(x)=(x/p)*(p-1)82ppt课件The Luckiest number POJ3696题目大意:定义:只含有数字8的数为幸运数给定正整数L,求L的所有倍数中最小的幸运数的位数83ppt课件The Luckiest number算法思路:设最终答案为x,则x满足(10 x-1)*8/90(mod L)化简上述式子:=(10 x-1)*80(mod 9L)=10 x-10(mod 9L/gcd(9L,8)=10 x1(mod 9L/gcd(9L,8)令m=9L/gcd(9L,8),若gcd(10,m)1,显然无解若gcd(10,m)=1,由欧拉定理:10(m)1(mod m)不过,我们要求的是最小解,而(m)只是一个可行解可以证明,最小解一定是(m)的一个约数将(m)分解质因数后枚举所有约数即可84ppt课件GCD&LCM Inverse POJ2429题目大意:已知两个正整数的最大公约数和最小公倍数,求这两个数若有多解输出和最小的一组85ppt课件GCD&LCM Inverse算法思路:令x=lcm/gcd将x分解质因数-Pollard rho方法枚举将x分解为两个互素的数相乘86ppt课件Cow Sorting POJ3270题目大意:n个两两不同的数排成一列,要求将这些数按升序排列操作:交换两个数x,y的位置,需要x+y的费用求需要的最小费用87ppt课件Cow Sorting算法思路:联想到轮换不同的轮换相互间是没有关系的,可以分别处理一个轮换,有两种处理方法:(1)用轮换中最小的元素依次与各元素交换,直到所有元素归位(2)用轮换中最小的元素与所有数中最小的元素交换,然后用所有数中最小的元素依次与各元素交换,直到所有元素归位可以证明,最优的方案一定是上述两者之一88ppt课件Necklace of Beads POJ1286题目大意:将三种不同颜色的珠子串成有n个珠子的项链,旋转/翻转后相同的算同一种,求方案数89ppt课件Necklace of Beads算法思路:直接套用Polya定理的结论即可计算置换的循环数的快速方法:旋转:n个点顺时针(或逆时针)旋转i个位置的置换,循环数为gcd(n,i)翻转:n为偶数且对称轴不过顶点:轮换个数为n/2;n为偶数且对称轴过顶点:轮换个数为n/2+1;n为奇数:轮换个数为(n+1)/290ppt课件S-Nim POJ2960题目大意:n堆石子,已知每堆石子的数量有一个集合S,S中有k个正整数两个人轮流从这些石子堆中取石子,规则:(1)每次只能从一堆里取(2)取出石子的数量值是S中的一个元素(3)不能按规则取石子者负求先手必胜还是必败91ppt课件S-Nim算法思路:若只有一堆石子-SG函数值根据集合S构造有向无环图多堆石子,任意两堆石子相互独立-游戏的和只要求出每堆石子的SG函数值,异或起来即为整个游戏的SG值92ppt课件EXTENDED LIGHTS OUTPOJ1222题目大意:5*6的灯阵,已知初始时每盏灯的开关状态每盏灯后面有一个按钮,按下按钮后,相应的灯及其上下左右的灯的开关状态都会改变求关掉所有灯的一种可行方案93ppt课件EXTENDED LIGHTS OUT算法思路:把每个按钮的使用次数设为未知数,注意到一个按钮使用两次等于没用,因此使用次数只能是0或1对于每盏灯,都可以列出一个xor方程接下来就是利用高斯消元来解这个xor方程组了94ppt课件High-Dimensional Vector Correspondence POJ3707题目大意:给定两个m维向量组p1,p2,.,pn和q1,q2,.,qn,求能否经过一系列的翻转和旋转操作,使得p1,p2,.,pn变成q1,q2,.,qn95ppt课件High-Dimensional Vector Correspondence算法思路:仔细分析题目可以看出,本题实际上是给定两个矩阵P和Q,要求一个正交矩阵H,使得HP=Q利用施密特正交化,将P分解P=TU,其中T为正交矩阵,U为上三角矩阵(注意P的秩可能小于n)令A=HT,则AU=Q,转置得UA=Q,此时U为下三角矩阵用类似高斯消元的办法求出A(注意无解和无穷多解的情况)通过逆矩阵的一些相关知识即可求出H96ppt课件97ppt课件