1、浙江林学院浙江林学院ACMACM集训队阶段总结集训队阶段总结Write by Zhuangli(zjfc3)图论图论What is that?什么是图论?n图论图论Graph TheoryGraph Theory是数学的一个分支。它以图为是数学的一个分支。它以图为研究对象。图论中的图是由若研究对象。图论中的图是由若 干给定的点及连接两点干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系线表示相应两个事物间具有这
2、种关系 。n图论本身是应用数学的一部份，因此，历史上图论曾图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉字记载最早出现在欧拉17361736年的论着中，他所考虑的年的论着中，他所考虑的原始问题有很强的实际背景。原始问题有很强的实际背景。并查集及其拓展并查集及其拓展n并查集是一种信息内聚很强的数据结构，它在判定图并查集是一种信息内聚很强的数据结构，它在判定图的连通性以及等价类划分的时空效率上有着不可替代的连通性以及等价类划分的时空效率上有着不可替代的优势。但并查集的特殊应用也应该有所了
3、解的优势。但并查集的特殊应用也应该有所了解.以下两类是并查集在实际问题中的特殊拓展，希望大以下两类是并查集在实际问题中的特殊拓展，希望大家能够进行快速掌握家能够进行快速掌握.n1.1.集合计数问题集合计数问题n2.2.二分图识别二分图识别集合计数问题集合计数问题nHDU 1856 More is better题意：题意：若若A与与B认识，认识，B与与C认识，则认识，则A与与C认识，现给认识，现给你一组人员的关系表，求在这样的不同群组内，你一组人员的关系表，求在这样的不同群组内，拥有最多人数群组的人数拥有最多人数群组的人数。集合计数问题集合计数问题n有什么想法？有什么想法？n并查后统计并查数组并
4、查后统计并查数组?n不可行不可行 数据范围数据范围10000000 10000000 如果逐个统如果逐个统计必定计必定TLE TLE 不能如此暴力不能如此暴力.n思路如何思路如何想想3 3分钟分钟集合计数问题集合计数问题n联想到并查集的构造原理n构造rank数组,在并操作中入手！n好,问题解决!二分图识别二分图识别nHDU 1829 A Bug Of LifeHDU 1829 A Bug Of Lifen题意：题意：假定两只飞虫假定两只飞虫(Bug)(Bug)关系表，如关系表，如A BA B表示表示A A仰慕仰慕B B，问是否存在同性的飞虫互相仰慕（也就是同性问是否存在同性的飞虫互相仰慕（也就
5、是同性恋问题）恋问题）.二分图识别二分图识别n难点：难点：A与与B的集合归属不定的集合归属不定n如何解决如何解决?思考！思考！二分图识别二分图识别n非此即彼思想的运用非此即彼思想的运用n构造数组构造数组oppopp，初始化为本身编号，若，初始化为本身编号，若A A与与B B有关，首先有关，首先进行进行find(A),find(Bfind(A),find(B)的操作，若根相同，则说明的操作，若根相同，则说明A A与与B B属于同一集合，即同性恋，否则执行下面的操作，如属于同一集合，即同性恋，否则执行下面的操作，如果果A A的的oppopp等于本身，说明等于本身，说明A A的的oppopp未初始化
6、，使之等于未初始化，使之等于B B，否则将否则将A A的的oppopp与与B B进行进行UnitionUnition操作，类似的如果操作，类似的如果B B的的oppopp等于本身，说明等于本身，说明B B的的oppopp未初始化，使之等于未初始化，使之等于A A，否，否则将则将B B的的oppopp与与A A进行进行UnitionUnition操作操作二分图识别二分图识别n想想为什么？想想为什么？n二分图的性质决定二分图的性质决定n更深入的二分识别更深入的二分识别(如统计最小单元集，如统计最小单元集，如何进行如何进行 _ 课后思考课后思考!)!)最短路径问题最短路径问题n在一个网络图中求解一点
7、到另一点间最短距离及其路径的算法称之为最短路径问题。n1、单源正权最短路径n2、单源带负权最短路径n3、多源最短路径单源正权最短路径单源正权最短路径n求解单源最短路径的求解单源最短路径的DijkstraDijkstra算法，状态转移与贪心准则的完美算法，状态转移与贪心准则的完美结合。结合。n思想：动态规划思想：动态规划 n策略：贪心策略：贪心(O(Ve(O(Ve)n步骤：步骤：1.1.构造辅助数组构造辅助数组Dis,Vist,DisiDis,Vist,Disi 表示从源点出发到达表示从源点出发到达i i点的点的最短距离最短距离,Visti,Visti 表示表示i i点是否已被访问，算法开始执行
8、时令所点是否已被访问，算法开始执行时令所有有Disi=w(start,iDisi=w(start,i)不可达为不可达为MAX,ViststartMAX,Viststart=true.=true.2.2.每次得到每次得到DisDis数组中最小且未被访问过的点数组中最小且未被访问过的点i i，标记，标记VistiVisti=true,=true,遍历所有与遍历所有与i i相关的边，若得到相关的边，若得到Disi+w(i,j)DisjDisi+w(i,j)Disj，则更新，则更新Disj=Disi+w(iDisj=Disi+w(i,j).,j).3.3.如此循环直到所有点均被标记如此循环直到所有点均
9、被标记.单源正权最短路径单源正权最短路径nDijkstraDijkstra的致命弱点：不能处理带负权的边的致命弱点：不能处理带负权的边n思考：思考：Why?Why?n问题出自贪心策略！若存在负权，则算法将问题出自贪心策略！若存在负权，则算法将不断更新负权边相关顶点的不断更新负权边相关顶点的DisDis值，从而导致值，从而导致答案错误答案错误!单源带负权最短路径单源带负权最短路径n如何处理如何处理DijkstraDijkstra的遗留问题？的遗留问题？n摈弃贪心策略摈弃贪心策略 执行松弛技术执行松弛技术-Bellman-fordBellman-ford算法算法单源带负权最短路径单源带负权最短路径
10、n什么是松弛技术？什么是松弛技术？n日常生活中的例子日常生活中的例子（1+11+1猜想）猜想）n松弛技术的本质是首先给予一个物体很松弛技术的本质是首先给予一个物体很高的估价，在每次的迭代中对估价进行高的估价，在每次的迭代中对估价进行修正，在有限次的迭代后使估价与实际修正，在有限次的迭代后使估价与实际值吻合的技术。值吻合的技术。单源带负权最短路径单源带负权最短路径n思想：若存在思想：若存在N N个点的网络，则对于起点个点的网络，则对于起点到终点最多经过到终点最多经过N-1N-1条边条边n策略：有限迭代下的松弛技术策略：有限迭代下的松弛技术单源带负权最短路径单源带负权最短路径n步骤：步骤：n1 1
11、、开辟辅助数组、开辟辅助数组DisDis,记录源点到点记录源点到点i i的最小距离，的最小距离，初始时设所有初始时设所有DisDis值为值为MAXMAX，DisstartDisstart=0.=0.n2 2、进行、进行n-1n-1次迭代，对于所有边，若满足次迭代，对于所有边，若满足DisiMAX&Disi+w(i,j)DisjDisiMAX&Disi+w(i,j)Disj,更新更新Disj=Disj=Disi+w(i,jDisi+w(i,j).).n3 3、执行完成后，再执行、执行完成后，再执行1 1次迭代，若出现次迭代，若出现Disi+w(i,j)DisjDisi+w(i,j)Disj 的情
12、况，则表明出现了负环，的情况，则表明出现了负环，此时不存在最短路径，否则此时不存在最短路径，否则DisendDisend 即所求单源最短即所求单源最短路径路径.单源带负权最短路径单源带负权最短路径n算法分析：算法分析：n1 1、迭代、迭代v-1v-1次，每次遍历所有边次，每次遍历所有边,复杂度复杂度O O（VEVE）,E,E为全部边，为全部边，DijkstraDijkstra的复杂度的复杂度O(Ve),eO(Ve),e为部分边为部分边.效率差别很大效率差别很大!n2 2、如何优化？思考！、如何优化？思考！单源带负权最短路径单源带负权最短路径n优化优化1 1：使用：使用boolbool值值Y Y
13、 标记此次迭代是否进行松弛，若标记此次迭代是否进行松弛，若没进行松弛表明已经得到最短路径，因此跳出循环。没进行松弛表明已经得到最短路径，因此跳出循环。（常系数优化）（常系数优化）-YEN-YEN氏优化氏优化n优化优化2 2：使用标记数组以及队列辅助，初始化时推入：使用标记数组以及队列辅助，初始化时推入startstart点，标记点，标记startstart在队内，每次执行时，将队首推在队内，每次执行时，将队首推出，标记其不在队内，遍历其邻边，进行松弛操作，出，标记其不在队内，遍历其邻边，进行松弛操作，将所有不在队内且进行过松弛操作的边相关的点入队将所有不在队内且进行过松弛操作的边相关的点入队直
14、到队列为空（即不再进行松弛操作）直到队列为空（即不再进行松弛操作）-SPFA-SPFA！单源带负权最短路径单源带负权最短路径n由优化由优化2得到的正是传说中的得到的正是传说中的SPFA，拥有神一般的效，拥有神一般的效率率O（KE），），K一般取值一般取值3-5。算法如其名。算法如其名Shortest Path Fast Algorithm!n瓶颈：如何判负环？思考！瓶颈：如何判负环？思考！n当一个点入队次数超过边的次数！需要辅助数组统计当一个点入队次数超过边的次数！需要辅助数组统计各点入队次数，此时的空间与时间效率都极低！因各点入队次数，此时的空间与时间效率都极低！因此此算法在稠密带负环图中的
15、表现不如此此算法在稠密带负环图中的表现不如bellman-ford的的YEN氏优化！请大家慎重选择使用。氏优化！请大家慎重选择使用。多源最短路径多源最短路径n当题目要求大量的查询工作时，需要一种算法当题目要求大量的查询工作时，需要一种算法能在多项式时间内得到所有顶点间的最短距离能在多项式时间内得到所有顶点间的最短距离并保存结果备查。并保存结果备查。nFloyedFloyed算法应运而生算法应运而生!多源最短路径多源最短路径n思想：传递关系闭包思想：传递关系闭包n策略：动态规划策略：动态规划O(VO(V*V V*V)V)n步骤：步骤：n1 1、对于点、对于点k k，若存在，若存在w(i,k)+w
16、(k,j)w(i,jw(i,k)+w(k,j)=(=(或或=)C=)C（常数）（常数）,以此为模型构成的约束系统，称之为差分约束以此为模型构成的约束系统，称之为差分约束系统。系统。差分约束初步差分约束初步n首先我们回顾下松弛技术，在首先我们回顾下松弛技术，在Bellman-FordBellman-Ford算算法中，有一个十分关键的三角不等式法中，有一个十分关键的三角不等式Disi+w(i,j)DisjDisi+w(i,j)Disj 使得迭代结束后所有的使得迭代结束后所有的Disj=Disi+w(i,jDisj=（或（或=）C C，我们取，我们取=情况研究情况研究,则则要求要求xi-xjxi-x
17、j=C=C，即，即xi=xj+Cxi=wi,jAi+Bj=wi,j 始终始终 成立。成立。KMKM算法的正确性基于以下定理：算法的正确性基于以下定理：若由二分图中所有满足若由二分图中所有满足Ai+Bj=wi,jAi+Bj=wi,j 的边的边(i,j(i,j)构成的子图构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。最大权匹配。这个定理是显然的。因为对于二分图的任意一个匹配，如果它包这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于相等子图，那么它的边权和等于所有顶点的顶标和；如果它含于相等子图，那么
18、它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最大权匹配。和。所以相等子图的完备匹配一定是二分图的最大权匹配。n算法的本质是对匈牙利算法的改进，但实际上却比匈牙利算法早算法的本质是对匈牙利算法的改进，但实际上却比匈牙利算法早发表几年，其核心仍然是寻找增广路径的过程。发表几年，其核心仍然是寻找增广路径的过程。KM算法算法n步骤步骤n初始时为了使初始时为了使Ai+Bj=wi,jAi+Bj=wi,j 恒成立，令恒成立，令AiAi 为所有与顶点为所有与顶点Xi
19、Xi关联的边的最大权，关联的边的最大权，BjBj=0=0。如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，。如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。直到相等子图具有完备匹配为止。n我们求当前相等子图的完备匹配失败了，是因为对于某个我们求当前相等子图的完备匹配失败了，是因为对于某个X X顶点，我们找不到一条从它出发顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点全部是的交错路。这时我们获得了一棵交错树，它的叶子结点全部是X X顶点。现在我们把交错树中顶点。现在我们把交错树中X X顶点
20、的顶标全都减小某个值顶点的顶标全都减小某个值d d，Y Y顶点的顶标全都增加同一个值顶点的顶标全都增加同一个值d d，那么我们会发现：，那么我们会发现：n两端都在交错树中的边两端都在交错树中的边(i,j(i,j)，Ai+BjAi+Bj 的值没有变化。也就是说，它原来属于相等子图，的值没有变化。也就是说，它原来属于相等子图，现在仍属于相等子图。现在仍属于相等子图。n两端都不在交错树中的边两端都不在交错树中的边(i,j(i,j)，AiAi 和和BjBj 都没有变化。也就是说，它原来属于（或不属都没有变化。也就是说，它原来属于（或不属于）相等子图，现在仍属于（或不属于）相等子图。于）相等子图，现在仍
21、属于（或不属于）相等子图。nX X端不在交错树中，端不在交错树中，Y Y端在交错树中的边端在交错树中的边(i,j(i,j)，它的，它的Ai+BjAi+Bj 的值有所增大。它原来不属于的值有所增大。它原来不属于相等子图，现在仍不属于相等子图。相等子图，现在仍不属于相等子图。nX X端在交错树中，端在交错树中，Y Y端不在交错树中的边端不在交错树中的边(i,j(i,j)，它的，它的Ai+BjAi+Bj 的值有所减小。也就说，它原的值有所减小。也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。n现在的问
22、题就是求现在的问题就是求d d值了。为了使值了。为了使Ai+Bj=wi,jAi+Bj=wi,j 始终成立，且至少有一条边进入相等子始终成立，且至少有一条边进入相等子图，图，d d应该等于应该等于minAi+Bj-wi,j|XiminAi+Bj-wi,j|Xi在交错树中，在交错树中，YiYi不在交错树中不在交错树中。n理解原理就行，在一般情况下理解原理就行，在一般情况下KMKM算法的代码不会调整，因此只要会使用模版，一切不在话下，算法的代码不会调整，因此只要会使用模版，一切不在话下，当然图论本身就是充满了建模的思想，只有好的模型才能有真正的效率！当然图论本身就是充满了建模的思想，只有好的模型才能
23、有真正的效率！KM算法算法n效率效率 O O（V V*V V*V V）nKMKM算法的本质，对于算法的本质，对于N N*N N的矩阵每行每列的矩阵每行每列只能取一个数，使其和为最大！只能取一个数，使其和为最大！强连通分支强连通分支n什么是强连通分支？什么是强连通分支？n强连通分支就是任意两点均可达的有向强连通分支就是任意两点均可达的有向子图。子图。n理论：白色路径定理理论：白色路径定理n求解：求解：TarjanTarjan算法算法强连通分支强连通分支n什么是时间戳？什么是时间戳？nDFSDFS进行时，访问到节点所花的时间进行时，访问到节点所花的时间n算法理论依据：算法理论依据：DFSDFS时，
24、如果所达的下一个点时，如果所达的下一个点i i已经被访问，则从该点已经被访问，则从该点j j出发，寻找父节点到出发，寻找父节点到i i，其间所经过的所有点必为以其间所经过的所有点必为以i i为代表的强连通为代表的强连通分支上的点分支上的点(并查实现并查实现)n如何判断是否是该次被访问？时间戳！如何判断是否是该次被访问？时间戳！强连通分支强连通分支n步骤步骤n对于每个顶点，设立对于每个顶点，设立NumNum、LowLow、UsedUsed、AliveAlive四个属性，一个四个属性，一个StackStack保存当前正在被遍历的顶点；保存当前正在被遍历的顶点；n每访问一个顶点，将它的每访问一个顶点
25、，将它的NumNum和和LowLow设立为当前时间戳，设立为当前时间戳，UsedUsed、AliveAlive设为设为TrueTrue，并将顶点入栈；，并将顶点入栈；n对于它的每条边，若边的终点未对于它的每条边，若边的终点未UsedUsed，则访问，而后用终点的，则访问，而后用终点的LowLow值更新它的值更新它的LowLow值，对于每个值，对于每个UsedUsed且且AliveAlive的终点，用它的的终点，用它的NumNum值更新当前值；值更新当前值；n访问完毕当前顶点后，若访问完毕当前顶点后，若LowLow与与NumNum相等，说明找到了一个强连通相等，说明找到了一个强连通分量，它包括栈
26、中所有在当前顶点上方的顶点，将它们出栈并记分量，它包括栈中所有在当前顶点上方的顶点，将它们出栈并记下下BelongBelong值，出栈的顶点的值，出栈的顶点的AliveAlive要置为要置为falsefalse。n扫描各点扫描各点BelongBelong值，其代表的点的个数便为强连通分支数！值，其代表的点的个数便为强连通分支数！强连通分支强连通分支n应用应用n1 1、求解单纯问题、求解单纯问题 HDU 1269HDU 1269n2 2、缩图技术、缩图技术 (适用于多点多边的关系闭包求解适用于多点多边的关系闭包求解)待研究的问题待研究的问题n次小生成树次小生成树n最优比例生成树最优比例生成树n最
27、小树型图最小树型图n弦图弦图n稳定婚姻问题稳定婚姻问题数论数论Its easy to learn!数论数论n什么是数论？什么是数论？n数论是研究整数性质的一门很古老的数学分支，数论是研究整数性质的一门很古老的数学分支，其初等部分是以整数的整除性其初等部分是以整数的整除性为中心的，包括整除性、不定方程、同余式、连分数、素数（即整数）分布为中心的，包括整除性、不定方程、同余式、连分数、素数（即整数）分布 以以及数论函数等内容，统称初等数论（及数论函数等内容，统称初等数论（elementary number theoryelementary number theory）。）。n初等数论的大部份内容早
28、在古希腊欧几里德的初等数论的大部份内容早在古希腊欧几里德的 几何原本几何原本中就已出现。欧几中就已出现。欧几里得证明了素数有无穷多个，他还给出求两个自然数的最大公约数的方法，里得证明了素数有无穷多个，他还给出求两个自然数的最大公约数的方法，即即所谓欧几里得算法。我国古代在数论方面亦有杰出之贡献，现在一般数论书中的所谓欧几里得算法。我国古代在数论方面亦有杰出之贡献，现在一般数论书中的中国剩余定理正是我国古代中国剩余定理正是我国古代孙子算经孙子算经中的下卷第中的下卷第2626题，我国称之为题，我国称之为 孙子定理。孙子定理。n近代初等数论的发展得益于费马、欧拉、拉格朗日、勒让德和高斯等人的工作。近
29、代初等数论的发展得益于费马、欧拉、拉格朗日、勒让德和高斯等人的工作。18011801年，高斯的年，高斯的算术探究算术探究是数论的划时代杰作。高斯还提出：数学是科学是数论的划时代杰作。高斯还提出：数学是科学的皇后，数论是数学中的皇冠。可见高斯对数论的高度评价。的皇后，数论是数学中的皇冠。可见高斯对数论的高度评价。n由于自由于自2020世纪以来引进了抽象数学和高等分析的世纪以来引进了抽象数学和高等分析的 巧妙工具，数论得到进一步的巧妙工具，数论得到进一步的发展，从而开阔了新的研究领域，出现了代数数论、解析数论、几何数论等发展，从而开阔了新的研究领域，出现了代数数论、解析数论、几何数论等 新新分支。
30、而且近年来初等数论在计算器科学、组合数学、密码学、代数编码、计算分支。而且近年来初等数论在计算器科学、组合数学、密码学、代数编码、计算方法等领域内更得到了广泛的应用，无疑同时间促进着数论的发展。方法等领域内更得到了广泛的应用，无疑同时间促进着数论的发展。同余定理同余定理n对于正整数对于正整数a,b,ca,b,cn(a%c+b%c)%c=(a+b)%c(a%c+b%c)%c=(a+b)%cn(a(a*b)%c=(a%cb)%c=(a%c*b%c)%cb%c)%cn注意对于除法与减法注意对于除法与减法%运算为非封闭运算运算为非封闭运算 需要进行数论变换才能继续进行下去需要进行数论变换才能继续进行下
31、去同余定理同余定理n大数求余大数求余n设大数设大数R=a1R=a1*100+a2100+a2*101+101+.+an.+an*10n-110n-1n则则R%C=(a1R%C=(a1*100%C+a2100%C+a2*101%C+101%C+.+an.+an*10n-10n-1%C)%C1%C)%Cn可以在可以在O O（lognlogn）时间内解决大数求余问题）时间内解决大数求余问题n步骤：步骤：n以字符读入大数后，设置计数器以字符读入大数后，设置计数器sum=0 sum=0 nsum=(10sum=(10*sum+keyi-0)%C;sum+keyi-0)%C;n迭代后令迭代后令sum=su
32、m%Csum=sum%C;GCDnGCDGCD（最大公约数）的一般求解（最大公约数）的一般求解n欧几里德辗转相除法（必须掌握）欧几里德辗转相除法（必须掌握）nIf(a%bIf(a%b=0)return b;=0)return b;Else return gcd(b,a%bElse return gcd(b,a%b););本过程具有收敛性质本过程具有收敛性质扩展欧几里德扩展欧几里德n在一些具体的题目中，我们还需要的到一组满在一些具体的题目中，我们还需要的到一组满足足ax+by=gcd(a,bax+by=gcd(a,b)的最小解，用以判断模方程的最小解，用以判断模方程是否有解，此时就要使用扩展欧几
33、里德是否有解，此时就要使用扩展欧几里德.n相比一般欧几里德方法，扩展欧几里德有一个相比一般欧几里德方法，扩展欧几里德有一个对于对于X X，Y Y求解的递推过程。使用递归实现，递求解的递推过程。使用递归实现，递归条件为归条件为b=0b=0时，时，X=1,Y=0;X=1,Y=0;否则否则t=X;X=Y;t=X;X=Y;Y=t-(a/bY=t-(a/b)*X;(X;(递推求得递推求得)可以证明最后出来的可以证明最后出来的X X，Y Y必然是最小解必然是最小解.n应用：模线性方程的求解应用：模线性方程的求解循环群生成元循环群生成元n对于对于mod nmod n域中的任意数域中的任意数a a，若有，若有
34、gcd(m,ngcd(m,n)=1)=1，则，则m m为该域的生成元，使得为该域的生成元，使得a+kma+km可以为域中任意数可以为域中任意数.n证明十分简单，若证明十分简单，若gcd(m,ngcd(m,n)=1)=1，则，则lcm(m,nlcm(m,n)=m)=m*n,n,则对于则对于a a的的mod nmod n运算运算,需需要要n n次的计算才能回到次的计算才能回到a a，期间必遍历该，期间必遍历该域中所有数！域中所有数！因子分解因子分解n对于筛选大量数的因子分解工作，可以对于筛选大量数的因子分解工作，可以与筛选质数同时进行。与筛选质数同时进行。n令令lenileni 记录数记录数i i
35、的因子个数，则对于每的因子个数，则对于每个素数个素数p p的倍数及本身，插入因子的倍数及本身，插入因子p p，并，并使使lenlen值增长，筛选完所有素数后就完成值增长，筛选完所有素数后就完成了因子分解了因子分解素数判定素数判定n对于一千万内素数的判定：对于一千万内素数的判定：n筛选法最优筛选法最优n对于一千万外素数的判定：对于一千万外素数的判定：n米勒测试米勒测试筛选法筛选法n给定辅助给定辅助boolbool数组数组primeprime，首先全置，首先全置true,true,使使prime0=prime1=false;prime0=prime1=false;n遍历，当遇到遍历，当遇到prim
36、eiprimei=true,=true,将之小于将之小于n n的所有倍数置的所有倍数置falsefalse；n最后一次遍历，所有值为最后一次遍历，所有值为truetrue的数即为的数即为素数！素数！n时空效率时空效率 均摊相关伪线性复杂度均摊相关伪线性复杂度米勒测试米勒测试n理论基础理论基础费马定理费马定理n实践工具实践工具二分求幂二分求幂米勒测试米勒测试n费马定理：费马定理：n若若p p为素数为素数-a(p-1)%p=1-a(p-1)%p=1n注意此定理只为充分注意此定理只为充分 不为必要不为必要n米勒测试以概率的形式避免了误判的发生米勒测试以概率的形式避免了误判的发生 从从严格意义上来说米
37、勒测试的意义并不科学严格意义上来说米勒测试的意义并不科学 但但是实际证明在可数范围内的伪素数十分之少是实际证明在可数范围内的伪素数十分之少 而且同时满足而且同时满足a=2,a=3,a=7a=2,a=3,a=7的底的伪素数更是的底的伪素数更是少得可怜，因此该测试从概率上满足了快速判少得可怜，因此该测试从概率上满足了快速判定素数的需求。定素数的需求。米勒测试米勒测试n二分快速求幂模原理二分快速求幂模原理n对于对于res=ab%cres=ab%c的求解的求解n若若b%2=0b%2=0则则res=(a(b/2)%cres=(a(b/2)%c*(a(b/2)%c)%c(a(b/2)%c)%cn否则否则r
38、es=(ares=(a*(a(b/2)%c(a(b/2)%c*(a(b/2)%c)%c(a(b/2)%c)%c欧拉函数欧拉函数n设设E(nE(n)为为n n以内（不包括以内（不包括n n）与）与n n互质数的互质数的个数，则个数，则E(nE(n)称为关于称为关于n n的欧拉函数。的欧拉函数。n欧拉函数的求法，对于欧拉函数的求法，对于n=p1n=p1*p2p2*p3p3pnpnnE(nE(n)=n)=n*(1-1/p1)(1-1/p1)*(1-1/p2)(1-1/p2)*(1-1/pn)(1-1/pn)n可以以容斥原理证明其正确性！可以以容斥原理证明其正确性！n欧拉定理欧拉定理:a(E(n)%n
39、:a(E(n)%n=1=1模线性方程求解模线性方程求解naxb(modaxb(mod n)n)有解，当且仅当有解，当且仅当b%gcd(a,nb%gcd(a,n)=0)=0n使用扩展欧几里德求得使用扩展欧几里德求得d=gcd(a,nd=gcd(a,n),),则则aX+nY=d,x=(XaX+nY=d,x=(X*(b/d)%n(b/d)%nnWhy?Why?nb/d=m a(Xb/d=m a(X*m)+nYm)+nY*m=b=x=(Xm=b=x=(X*m)%nm)%n中国剩余定理中国剩余定理n设设 n=n1n=n1*n2.nkn2.nk,其中因子两两互质其中因子两两互质.有有:a-(a1,a2,.
40、,aka-(a1,a2,.,ak),),其中其中ai=a mod niai=a mod ni,则则 a a和和(a1,a2,.,ak(a1,a2,.,ak),),关系是一一对应的关系是一一对应的.就就是说可以由是说可以由 a a求出求出(a1,a2,.,ak(a1,a2,.,ak),),也可以由也可以由(a1,a2,.,ak(a1,a2,.,ak)求出求出a an求解：求解：n中国古代演算法中国古代演算法n模线性方程代入模线性方程代入中国剩余定理中国剩余定理n应用应用n大整数表示大整数表示n快速运算快速运算连分数逼近连分数逼近n在数学中，连分数或繁分数即如上表达式在数学中，连分数或繁分数即如上
41、表达式.n这里的这里的 a0 a0 是某个整数而所有其他的数是某个整数而所有其他的数 an an 都是正整数。可依样定义出都是正整数。可依样定义出更长的表达式。如果部分分子（更长的表达式。如果部分分子（partial numeratorpartial numerator）和部分分母）和部分分母（partial denominatorpartial denominator）允许假定任意的值，在某些上下文中可以包）允许假定任意的值，在某些上下文中可以包含函数，则最终的表达式是广义连分数。在需要把上述标准形式与广义含函数，则最终的表达式是广义连分数。在需要把上述标准形式与广义连分数相区别的时候，可称
42、它为简单或正规连分数，或称为是规范形式连分数相区别的时候，可称它为简单或正规连分数，或称为是规范形式的的n一个数的连分数表示是有限的，当且仅当这个数是有理数。一个数的连分数表示是有限的，当且仅当这个数是有理数。n“简单简单”有理数的连分数表示是简短的。有理数的连分数表示是简短的。n任何有理数的连分数表示是唯一的，如果它没有尾随的任何有理数的连分数表示是唯一的，如果它没有尾随的 1 1。（但是。（但是 a0;a0;a1,.an,1=a0;a1,.an+1a1,.an,1=a0;a1,.an+1。）。）n无理数的连分数表示是唯一的。无理数的连分数表示是唯一的。n连分数的项将会重复，当且仅当它是一个
43、二次无理数（即整数系数的二连分数的项将会重复，当且仅当它是一个二次无理数（即整数系数的二次方程的实数解）的连分数表示。次方程的实数解）的连分数表示。n数数 x x 的截断连分数表示很早产生的截断连分数表示很早产生 x x 的在特定意义上的在特定意义上“最佳可能最佳可能”的有的有理数逼近。理数逼近。连分数逼近连分数逼近n意义意义n1 1、精度保留、精度保留n2 2、避免浮点运算、避免浮点运算n3 3、无理数的表示唯一、无理数的表示唯一n4 4、研究连分数的动机源于想要有实数在研究连分数的动机源于想要有实数在“数学上纯粹数学上纯粹”的表示。的表示。n求解求解n欧几里德变体！欧几里德变体！连分数逼近
44、连分数逼近n 数据结构数据结构Soul!数据结构数据结构n什么是数据结构什么是数据结构?n数据结构是计算机存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来更高数据结构是计算机存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率的算法。数据结构往往同高效的检索算法和索引技术有关。的运行或者存储效率的算法。数据结构往往同高效的检索算法和索引技术有关。n数据结构在计算机科学界至今没有标准的定义。个人根据各自的理解而有不同的表述方法：数据结构在计算机科学界至今没有标准的定义。个人根据各自的理解而有不同的表述方法：nSartaj SahniSartaj Sahn
45、i 在他的在他的数据结构、算法与应用数据结构、算法与应用一书中称：一书中称：“数据结构是数据对象，以及数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。函数来给出。”他将数据对象（他将数据对象（data objectdata object）定义为）定义为“一个数据对象是实例或值的集合一个数据对象是实例或值的集合”。nClifford A.ShafferClifford A.Shaffer 在在数据结构与算法分析数据结构与算法分析一书中的定义是：一书中
46、的定义是：“数据结构是数据结构是 ADTADT（抽（抽象数据类型象数据类型 Abstract Data TypeAbstract Data Type）的物理实现。的物理实现。”nLobert L.KruseLobert L.Kruse 在在数据结构与程序设计数据结构与程序设计一书中，将一个数据结构的设计过程分成抽象一书中，将一个数据结构的设计过程分成抽象层、数据结构层和实现层。其中，抽象层是指抽象数据类型层，它讨论数据的逻辑结构及其层、数据结构层和实现层。其中，抽象层是指抽象数据类型层，它讨论数据的逻辑结构及其运算，数据结构层和实现层讨论一个数据结构的表示和在计算机内的存储细节以及运算的实运算
47、，数据结构层和实现层讨论一个数据结构的表示和在计算机内的存储细节以及运算的实现。现。数据结构数据结构n为什么要使用数据结构为什么要使用数据结构?n1 1、便于理清结构，易于表示出一个实体、便于理清结构，易于表示出一个实体的内部属性与外部联系。的内部属性与外部联系。n2 2、更好利用实体特性，从而为算法高效、更好利用实体特性，从而为算法高效铺路。铺路。n3 3、强有力的数据结构，能够取代算法的、强有力的数据结构，能够取代算法的优势。优势。数据结构数据结构n数据结构的基本类型：数据结构的基本类型：n1 1、顺序表、顺序表n2 2、链表、链表n3 3、广义表、广义表n4 4、树、树n5 5、图、图n
48、6 6、串、串顺序表顺序表n顺序表是在内存上开辟的连续片段，每顺序表是在内存上开辟的连续片段，每个元素单元拥有固定大小，以此组织形个元素单元拥有固定大小，以此组织形成的数据结构。成的数据结构。n优点：优点：n1 1、随机存取、随机存取n2 2、索引唯一、索引唯一n3 3、结构简单、结构简单顺序表顺序表n一般应用：一般应用：n1 1、寄存数组（包括栈和队列）、寄存数组（包括栈和队列）n2 2、哈希数组、哈希数组n3 3、树状数组、树状数组寄存数组寄存数组n这是我们最常见的顺序表表现方式，一这是我们最常见的顺序表表现方式，一般的大数据量程序，如果不能有边读边般的大数据量程序，如果不能有边读边处理的
49、方法，就需要首先保留所有的输处理的方法，就需要首先保留所有的输入，从而能够在而后的过程中进行处理。入，从而能够在而后的过程中进行处理。n主要应用：主要应用：n1 1、各类算法的线性预处理、各类算法的线性预处理n2 2、保留线性逻辑关系、保留线性逻辑关系n3 3、记忆化辅助、记忆化辅助寄存数组寄存数组n优点：优点：n1 1、静态、静态n2 2、随机、随机n3 3、高效、高效n缺点：缺点：n1 1、插入与删除操作效率极度低下、插入与删除操作效率极度低下n2 2、内存分配不灵活、内存分配不灵活n技巧：技巧：n1 1、满足递推与、满足递推与DPDP内存需求内存需求n滚动数组滚动数组n2 2、满足图的快
50、速判重、满足图的快速判重n化行为数化行为数 状态压缩状态压缩哈希数组哈希数组n什么是哈希？什么是哈希？n从广义上说哈希是一种键值对应的操作，是从数域到从广义上说哈希是一种键值对应的操作，是从数域到值域的一一映射，也就是我们通常称其为哈希函数的值域的一一映射，也就是我们通常称其为哈希函数的由来。由来。n为什么哈希表可以用数组实现？为什么哈希表可以用数组实现？n数组满足哈希的数组满足哈希的3 3个必要条件：个必要条件：n1 1、键、键indexindexn2 2、值、值valuevaluen3 3、键值映射（、键值映射（index-valueindex-value）O O（1 1）哈希数组哈希数组
