ACM经典算法集：数论与图论详解

本文档主要探讨了在ACM竞赛中常用的一些算法，涵盖了数论算法和图论算法两大类别。首先，对于数论部分： 1. **最大公约数 (GCD)**: 提供了一个递归函数`gcd(a, b)`，通过欧几里得算法计算两个整数a和b的最大公约数。该函数通过不断用较小数去除较大数的余数，直到余数为0，此时较大数即为两者的最大公约数。 2. **最小公倍数 (LCM)**: 提供了求解两个整数a和b最小公倍数的函数`lcm(a, b)`。首先检查a是否小于b，然后交换数值，初始化lcm为较大的数，接着通过循环找到lcm除以b的余数为0时的值，即为最小公倍数。 3. **素数判定**: - 对于小范围内的整数n，设计了一个名为`prime(n)`的函数，通过试除法检查n是否为质数，如果n能被2到√n之间的任何整数整除，则返回false，否则为true。 - 对于longint范围内的素数查找，有一个名为`getprime`的子程序，创建一个布尔数组存储50000以内所有可能的素数，并使用筛法找出这些素数。同时，还提供了一个`prime(x: longint)`函数，用于判断给定的longint x是否为素数。 接下来是图论算法： 1. **最小生成树 (Minimum Spanning Tree, MST)**: 其中介绍了Prim算法，`prim(v0: integer)`函数用于构建图的最小生成树。它维护两个数组`lowcost`和`closest`，分别记录当前已知边的成本和最近的节点，通过迭代添加边来构建最小生成树。 Prim算法的核心步骤包括初始化成本最低的边（起点v0），更新节点的最低成本和最近节点，然后在未加入的节点中寻找与当前树相连的最低成本边，直到所有节点都加入或无更多可达节点。 这份文档提供了ACM竞赛中实用的数论和图论算法，对于参赛者理解和实现这些基础算法具有很高的参考价值。理解并掌握这些算法技巧，可以帮助解决实际问题中的数据结构和算法挑战。