ACM竞赛数论算法：快速幂、扩展欧几里得

"这篇资源主要涉及ACM竞赛中的数论算法，包括模板代码，如快速幂、大数分解、欧几里得算法及其扩展。核心算法有：扩展欧几里得算法(用于求逆元和最大公约数)，线性组合求解，大数乘法取模，快速幂运算以及简单的最大公约数计算。这些算法在解决数论问题和模算术中具有重要应用。" 在ACM编程竞赛中，掌握数论算法是至关重要的，因为它们经常用于解决各种数学问题，特别是与整数和模运算相关的题目。以下是这些算法的详细解释： 1. **扩展欧几里得算法 (extend_gcd)**：此算法用于求两个整数a和b的最大公约数（GCD）的同时，还能找到它们的贝祖等式解，即存在整数x和y使得ax + by = gcd(a, b)。在代码中，函数返回GCD并更新变量x和y以满足等式。 2. **线性组合 (combine)**：该函数结合两个模线性同余方程(m1*x + r1 = 0 mod mi 和 m2*y + r2 = 0 mod m2) 来求解新的模线性同余方程(mi*xi + ri = 0 mod mi) 的解。如果无法找到解，函数返回0。 3. **大数乘法取模 (mult_large)**：这是一个高效的算法，用于计算两个大整数a和b相乘后对给定模p的余数。它利用位操作来减少乘法次数，从而提高效率。 4. **快速幂运算 (fast_power)**：快速幂算法用于高效地计算一个数的幂，特别是当指数非常大时。它通过将指数n二进制分解，然后重复自乘并取模来实现。这个算法的时间复杂度为O(log n)。 5. **最大公约数 (GCD)**：这是最简单的欧几里得算法实现，用于计算两个数的最大公约数。通过递归地将较大数替换为两数的余数，直到余数为0，此时较小的数就是最大公约数。 在ACM竞赛中，熟练运用这些算法可以帮助解决诸如因数分解、模逆元计算、质数检测等问题。例如，扩展欧几里得算法可以用于求模逆元，这对于解决线性同余方程组或模算术下的除法非常重要。快速幂则常用于计算幂次和判断素数，而线性组合则可能出现在解决线性同余方程组的题目中。