NOI算法大全：数论与图论算法解析

"NOI算法大全包含了数论算法和图论算法等多个方面，旨在帮助学习者掌握计算机竞赛中的核心算法。 一、数论算法 1. 求两数的最大公约数 (Greatest Common Divisor, GCD) 在计算中，求两个整数 a 和 b 的最大公约数可以使用欧几里得算法，如上述代码所示。这个算法基于除法的性质，不断将较大的数除以较小的数，直到余数为0，此时较小的数即为最大公约数。 2. 求两数的最小公倍数 (Least Common Multiple, LCM) 最小公倍数可以通过两个数的乘积除以它们的最大公约数得到。在给定的代码中，首先判断 a 是否小于 b，如果小于则交换两者，然后使用 while 循环不断加 a 直到 lcm 可以被 b 整除。 3. 素数判断 A. 对于小范围内的数判断是否为素数，可以遍历从 2 到平方根(n) 的所有整数，如果 n 能被其中任意一个整数整除，则 n 不是素数。 B. 对于 longint 范围内的数，可以使用筛法（比如埃拉托斯特尼筛法）来预处理一定数量的素数，并存储在一个数组中，以便后续快速查询。 二、图论算法 1. 最小生成树 (Minimum Spanning Tree, MST) 图论中的最小生成树问题，如 Prim 算法所示，用于找到一个无向加权图的边集合，使得这些边连接了图中的所有顶点，并且这些边的总权重尽可能小。Prim 算法从一个起始顶点 v0 开始，逐步添加边，每次添加的边是当前未加入树中且连接两个不同树部分的边中权重最小的一条。 算法步骤： - 初始化：为每个顶点设置一个初始距离（如无穷大），除了起始顶点 v0 设置为0。 - 迭代：在每一步中，找出所有与当前树相邻且具有最小距离的顶点，将其加入树中，并更新其相邻顶点的距离。 - 继续这个过程，直到所有顶点都包含在树中。 以上只是 NOI 算法大全中的一部分，完整的资料还涵盖了更多算法，如动态规划、搜索算法、字符串处理等，是计算机竞赛学习者的重要参考资料。通过学习和掌握这些算法，可以提升解决复杂问题的能力，对编程竞赛和实际开发工作都有很大帮助。"