算法大全：数论与图论算法详解

"算法大全.pdf" 本文档主要涵盖了两个方面的算法：数论算法和图论算法。以下是这两个领域的详细解释： 一、数论算法 1. 求两数的最大公约数 (GCD)： 提供的代码使用了欧几里得算法来计算两个整数 `a` 和 `b` 的最大公约数。基本思想是，如果 `b` 为零，则 `a` 是 GCD；否则，继续用 `a` 除以 `b` 的余数作为新的 `b`，重复此过程。 2. 求两数的最小公倍数 (LCM)： 这个函数首先确保 `a` 不小于 `b`，然后通过不断加 `a` 直到 `lcm` 能被 `b` 整除来计算 LCM。由于 LCM 与 GCD 之间的关系是 `a * b = GCD(a, b) * LCM(a, b)`，因此可以更高效地实现 LCM，但这里使用的是直接方法。 3. 素数的求法： A. 对于小范围内的数字，可以通过检查从2到平方根的每个数是否能整除 `n` 来判断是否为素数。 B. 对于更大的范围，如 longint 类型，可以使用“筛选法”（例如埃拉托斯特尼筛法）来预先生成一定范围内的素数列表，并在需要时查询。 二、图论算法 1. 最小生成树： - Prim算法是一种用于寻找加权无向图的最小生成树的方法。它从一个起始节点 `v0` 开始，逐步添加边，每次选择连接当前树与未加入树的节点中权重最小的边。`lowcost` 和 `closest` 数组分别存储从起始节点到各个节点的最低成本和最近节点。 为了实现Prim算法，需要维护一个集合来保存已经加入最小生成树的节点，以及一个优先队列（或最小堆）来存储未加入树的节点及其到树的边的成本。每次从队列中取出成本最低的节点，并将其所有未被处理的邻接边更新到队列中。 这些算法在计算机科学和编程中具有广泛的应用，例如在数据压缩、加密、图形渲染、网络设计和优化等领域。掌握这些基础算法对于提高编程能力，解决复杂问题至关重要。在实际应用中，还需要考虑算法的时间复杂度和空间复杂度，以确保解决方案的效率。