NOIP竞赛必备：基础算法详解与检测函数

本资源主要关注NOIP竞赛中的基础算法，包括求最大公约数（GCD）、最小公倍数（LCM）以及判断整数是否为质数的相关函数和过程。以下是详细的解析： 1. **GCD 函数**: 这部分提供了计算两个整数 `a` 和 `b` 之间的最大公约数（GCD）的函数 gcd(a, b)。通过欧几里得算法实现，它递归地调用自身，直到 `b` 变为 0，此时 `a` 就是 GCD。这种方法基于数学原理：两个整数的最大公约数等于其中较小的那个与两数相除余数的最大公约数。 2. **LCM 函数**: LCM 函数用于找出两个整数 `a` 和 `b` 的最小公倍数。首先，确保 `a` 大于或等于 `b`。然后从 `a` 开始，不断将 `a` 加到 `lcm` 上，直到 `lcm` 能被 `b` 整除，此时 `lcm` 即为最小公倍数。 3. **质数判断函数**: prime(n) 函数用于检查一个整数 `n` 是否为质数。通过遍历从 2 到 `sqrt(n)` 的整数，如果找到能整除 `n` 的因子，则 `n` 不是质数；反之，`n` 是质数。另外，getprime() 函数提供了一个更高效的方法，预先计算出 50000 以内的所有质数，通过数组 `p` 来标记每个数是否为质数。 4. **Prime 数列提取**: getprime() 函数不仅计算质数，还存储在 `pr` 数组中，并返回一个函数 prime(x: longint) 来查找大于等于 `x` 的最小质数。通过 `pr` 数组，可以快速定位到满足条件的质数。 5. **Primality 检查函数**: prim(v0: integer) 函数实现了 Primality 检查，但这里的描述可能不完整，因为它涉及到一个名为 "低成本"（lowcost）和 "最近"（closest）的数组，以及变量 `i`, `j`, `k`, `min`。根据上下文推测，可能是用于解决图论问题中 Prim 算法（寻找有向图中的最小生成树）中的辅助函数，其中可能涉及邻接矩阵或邻接表，用于维护当前节点的最低成本和最接近已选择节点的节点。 总结起来，这份资料涵盖了 NOIP 中常用的几个基础算法，如数论中的 GCD 和 LCM 计算，以及质数判定方法，还有可能是图论中 Prim 算法的辅助函数。这些算法在算法竞赛、编程挑战或者解决实际问题时都有广泛的应用，对提高编程能力和算法理解十分关键。