算法竞赛模板：数论、图论、数据结构与API速查

"该资源包含了算法竞赛中常用的数论、图论、数据结构以及API相关的模板代码，包括快速幂、最大公约数(GCD)、逆元计算、除法取模、素数筛法以及素数前缀和等算法实现。" 在算法竞赛中，掌握高效的数学运算和数据结构处理是至关重要的。以下是这些模板代码所涉及的知识点详解： 1. **快速幂**：快速幂是一种用于计算大整数幂的高效算法。`fastpowmod`函数通过将指数b二进制分解，每次迭代时将底数a平方并累乘，然后根据指数的奇偶性决定是否乘以底数。这种方法的时间复杂度为O(log b)，远优于朴素的幂运算。 2. **最大公约数(Greatest Common Divisor, GCD)**：GCD是两个或多个整数的最大正公因数。`gcd`函数使用欧几里得算法求解，通过不断将较大的数替换为两数相除的余数，直到余数为0，此时较小的数即为GCD。 3. **逆元**：在模p意义下，一个数i的逆元是指满足i * inv[i] ≡ 1 (mod p)的数。在模运算中，逆元用于简化除法操作。`inv`数组预计算了1到n的每个数模p的逆元，这在需要进行模p除法时非常有用。 4. **除法取模**：`divmod`函数实现了除法取模的操作，即(a / b) % p，它通过快速幂计算模逆元，再进行模乘运算得到结果，避免了直接除法可能的溢出问题。 5. **素数筛法**：线性筛是一种优化过的埃拉托斯特尼筛法，用于找出一定范围内的所有素数。`getprime`函数首先初始化一个标记数组，然后遍历2到n，对每个未被划去的数i，将其标记为素数，并划去所有i的倍数。通过这种方式，可以高效地找到所有小于等于n的素数。 6. **素数前缀和**：在数论中，素数前缀和是前n个素数的和。在实际应用中，如计算某个范围内素数的和，素数前缀和可以减少重复计算。`sumprime`命名空间中的代码提供了计算素数前缀和的方法，但具体实现细节不完整。 这些模板代码对于参加算法竞赛的选手来说是宝贵的工具，它们可以帮助选手快速实现基础功能，专注于解决更复杂的问题。理解并熟练运用这些算法，可以在面对时间限制严格的竞赛题目时提高解题效率。