ACM竞赛中的数论知识与素数算法

"ACM数论" 在计算机科学竞赛，特别是ACM（国际大学生程序设计竞赛）中，数论是一个重要的知识领域。数论主要研究整数的性质，其在解决算法问题时经常发挥关键作用。以下是数论的一些基本概念和重要知识点： 1. **整除**：如果整数a和b满足b = ac（c为整数且a≠0），我们就说a整除b，记作ab ∣ 。如果a不能整除b，记作a⊥b。整除具有以下基本性质： - (1) 若ab ∣ 且ac ∣ ，则a ∣ (b+c) - (2) 若ab ∣ ，则对所有整数c，abc ∣ - (3) 若ab ∣ 且bc ∣ ，则ac ∣ （传递性） 2. **素数与合数**：素数是只有两个正因子1和本身的整数，例如2、3、5等。合数则是至少有三个因子（包括1和自身）的整数。如果n是合数，它必然有一个小于或等于其平方根的因子。 3. **素数判定**：朴素的素数判定方法是从2开始试除小于n的所有自然数，时间复杂度为O(n)。优化后的做法是检查小于n的平方根的数，时间复杂度为O(n1/2)。 4. **算术基本定理**：每个正整数都能唯一表示为素数的乘积，素数因子按从小到大顺序排列。 5. **最大公约数（GCD）与最小公倍数（LCM）**：GCD(a, b)是a和b的最大公约数，LCM(a, b)是它们的最小公倍数。两者之间存在关系：ab = GCD(a, b) × LCM(a, b)。若GCD(a, b) = 1，则称a和b互素。 6. **求解素数**： - 当n较小（如n <= 1000）时，可以使用一个循环嵌套，时间复杂度为O(n * sqrt(n))。 - 当n较大时，如n = 10,000,000，朴素方法效率低，可以采用更高效的算法，如埃拉托斯特尼筛法（Sieve of Eratosthenes）： - 最简单的素数筛法：创建一个布尔数组prime[]，标记所有素数。首先将所有偶数标记为非素数，然后从3开始，标记所有倍数为非素数，直至sqrt(n)。 - 改进的素数筛法：仅存储奇数，因为偶数中除了2外都不是素数，这样可以减少一半的存储需求。 通过理解并掌握这些基本的数论概念和算法，参赛者可以在ACM竞赛中解决涉及数论的问题，提高解决问题的效率和准确性。