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

本资源是一份针对ACM比赛的实用算法集，特别关注数论和图论两大领域，对于那些想要深入研究算法的朋友具有很高的参考价值。以下将详细介绍其中的部分核心知识点： **一、数论算法** 1. **最大公约数 (GCD)**: 提供了一个名为`gcd`的函数，用于计算两个整数`a`和`b`的最大公约数。算法采用欧几里得算法的思想，通过反复取余，直到余数为0，此时的除数即为最大公约数。 2. **最小公倍数 (LCM)**: 函数`lcm`计算两个数的最小公倍数，首先判断较小的数，并用较大的数替换较小数作为初始值。然后，通过循环找到满足`lcm`能被较小数整除的最小值。 3. **素数判定**: - **小范围判断**: 函数`prime`利用试除法检查一个整数`n`是否为质数，只需遍历到其平方根，如果能被整除，则返回`false`。 - **大范围素数生成**: `getprime`过程用于生成并存储50000以内的所有素数，通过埃拉托斯特尼筛法优化，提高了查找效率。`prime`函数则根据生成的素数列表判断任意`longint`范围内的数是否为素数。 **二、图论算法** 1. **最小生成树 (Minimum Spanning Tree, MST)**: - **Prim算法**: `prim`函数实现了Prim算法，该算法从起点`v0`开始，维护两个数组`lowcost`和`closest`，分别记录当前节点的最低成本和最近的未加入树的节点。通过不断添加与当前树相连且成本最低的新边，构建出最小生成树。 通过对这些算法的深入理解，参赛者可以在实际的ACM竞赛中提高解题速度和正确率，掌握数论和图论的基本操作技巧，为解决复杂问题提供强有力的支持。此外，这份资料还可能包括其他数据结构、搜索算法、动态规划等知识点，为全面提升编程技能提供了宝贵的学习资料。