OI竞赛C语言代码库：数论、图论与排序

"这是一份关于OI（奥林匹克信息学竞赛）的C语言代码集锦，包含基础的数论、图论和排序算法。" 在这份代码集中，我们可以看到以下几个重要的知识点： 1. **最大公约数 (Greatest Common Divisor, GCD)**: 使用欧几里得算法计算两个整数 `a` 和 `b` 的最大公约数。通过不断用较大的数除以较小的数并取余，直到余数为0，此时较小的数即为最大公约数。 ```c int gcd(int a, int b) { int r; while (b != 0) { r = a % b; a = b; b = r; } return a; } ``` 2. **最小公倍数 (Least Common Multiple, LCM)**: 通过最大公约数来计算两个整数 `a` 和 `b` 的最小公倍数，即 `a * b` 除以它们的最大公约数。 ```c int lcm(int a, int b) { int r, c; while (b != 0) { r = a % b; a = b; b = r; } return c / a; } ``` 3. **质数判断**: - 对于小数值，可以通过遍历2到平方根(a)之间的所有整数来判断是否为质数。如果 `a` 能被任何数整除，则不是质数。 ```c int is_prime_num(int a) { if (a < 2) return 0; int i, high = sqrt(a); for (i = 2; i <= high; i++) { if (!(a % i)) return 0; } return 1; } ``` - 对于大数值，可以利用已有的质数表（`check[]` 和 `prime[]`）进行快速判断。 4. **图论中的 primenumbersheet**: 这可能是用于创建素数筛，即Eratosthenes筛法，用于一次性找出一定范围内的所有质数。代码没有给出完整实现，但给出了一个基础结构。 5. **优化后的质数判断 (largenumbers)**: 对于大数值的质数判断，已经预先生成了10000以内的质数表，然后通过比较表中的质数与目标数的平方根来快速判断。 除了以上代码，集合可能还包含其他数论函数，如扩展欧几里得算法（用于求解线性同余方程）、图的遍历算法（如深度优先搜索或广度优先搜索）、排序算法（如快速排序、归并排序等）。这些基础算法在OI比赛中至关重要，帮助参赛者解决各种复杂问题。对于学习OI或准备相关竞赛的程序员来说，这份代码集锦是宝贵的参考资料。