奇数、偶数、约数、质数、最大公因数、最小公倍数概念及竞赛中常见定理
概念介绍
奇数
定义：不能被2整除的整数，即形如 (2k+1)（(k) 为整数）。
例子：1, 3, 5, -7, 9 等。
偶数
定义：能被2整除的整数，即形如 (2k)（(k) 为整数）。
例子：2, 4, 0, -6, 8 等。
约数（因数）
定义：若整数 (a) 能被整数 (b) 整除（无余数），则 (b) 是 (a) 的约数。
例子：6 的约数有 1, 2, 3, 6；8 的约数有 1, 2, 4, 8。
素数（质数）
定义：大于1的自然数，且仅能被1和它本身整除。
注意：素数与质数是同一概念的不同术语。
例子：2, 3, 5, 7, 11；1不是素数。
最大公因数（GCD）
定义：两个或多个整数共有约数中的最大值。
计算：分解质因数后取共有质因数的最小指数乘积。
例子：gcd(12, 18) = 6（12=2²×3，18=2×3²，取2¹×3¹）。
最小公倍数（LCM）
定义：两个或多个整数的最小的公共倍数。
计算：分解质因数后取所有质因数的最大指数乘积。
例子：lcm(6, 8) = 24（6=2×3，8=2³，取2³×3）。
总结
• 奇偶性：整数按能否被2整除分为奇数和偶数。
• 约数/因数：描述整除关系的数，如6的约数是1,2,3,6。
• 素数/质数：特指只有两个正约数的自然数（>1）。
• GCD & LCM：分别通过共有质因数的最小指数和最大指数计算，用于解决分数化简、周期问题等。
注意：术语“约数”与“因数”、“素数”与“质数”为同义词，在不同语境中交替使用。
以下是针对 奇数、偶数、约数、素数、最大公因数（GCD）、最小公倍数（LCM） 等概念的常见定理及其在编程竞赛中的应用，涵盖数论基础和经典算法：
1. 奇偶性
• 奇偶性判定定理
• 奇数：x & 1 == 1；偶数：x & 1 == 0（位运算快速判断）。
• 应用：快速判断数的性质，例如棋盘覆盖、数独合法性等。
• 奇偶性质定理
• 奇数 ± 奇数 = 偶数；偶数 ± 偶数 = 偶数；奇数 ± 偶数 = 奇数。
• 应用：构造数学问题中的矛盾条件（如无法排列成特定形式）。
2. 素数（质数）
• 埃拉托斯特尼筛法（Sieve of Eratosthenes）
• 定理：通过标记素数的倍数，高效筛选出 [2, n] 内的所有素数。
• 时间复杂度：O(n log log n)。
• 代码片段：
def sieve(n):
is_prime = [True] * (n+1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(n**0.5)+1):
if is_prime[i]:
for j in range(i*i, n+1, i):
is_prime[j] = False
return [i for i, val in enumerate(is_prime) if val]
• 应用：预处理素数表，用于分解质因数、区间素数统计等。
• 米勒-拉宾素性测试（Miller-Rabin Primality Test）
• 定理：基于费马小定理和二次探测定理的随机化算法，高效判断大数是否为素数。
• 时间复杂度：单次测试 O(k log^3 n)（k 为测试轮数）。
• 代码技巧：固定基数的确定性测试（如对 n < 2^64，选择特定基可确保正确性）。
• 应用：大数质数判断（如RSA加密）。
3. 约数（因数）
• 唯一分解定理（算术基本定理）
• 定理：每个整数 n > 1 可唯一分解为素数幂次乘积，如 n = p₁^a₁ × p₂^a₂ × ...。
• 应用：快速计算约数个数、约数和、GCD/LCM等。
• 约数个数定理
• 公式：若 n = p₁^a₁ × p₂^a₂ × ...，则约数个数为 (a₁+1)(a₂+1)...。
• 应用：求解因数数量问题（如求 n! 的因数个数）。
• 枚举约数的优化方法
• 定理：约数成对出现，只需遍历到 √n。
• 代码片段：
def get_divisors(n):
divisors = []
for i in range(1, int(n**0.5)+1):
if n % i == 0:
divisors.append(i)
if i != n // i:
divisors.append(n//i)
return sorted(divisors)
4. 最大公因数（GCD）与最小公倍数（LCM）
• 欧几里得算法（辗转相除法）
• 定理：gcd(a, b) = gcd(b, a % b)，直到 b=0。
• 时间复杂度：O(log min(a, b))。
• 代码片段：
def gcd(a, b):
return a if b == 0 else gcd(b, a % b)
• 应用：分数化简、线段相交判断等。
• 扩展欧几里得算法（Extended Euclidean Algorithm）
• 定理：求解 ax + by = gcd(a, b) 的整数解 (x, y)。
• 代码片段：
def extended_gcd(a, b):
if b == 0:
return a, 1, 0
g, x, y = extended_gcd(b, a % b)
return g, y, x - (a // b) * y
• 应用：求解线性同余方程（如 ax ≡ c (mod m)）、模逆元计算。
• 贝祖定理（Bézout’s Identity）
• 定理：若 gcd(a, b) = d，则存在整数 x, y 使得 ax + by = d。
• 推论：ax + by = c 有解当且仅当 d | c。
• 应用：判断方程是否有解，构造解集。
• LCM与GCD的关系
• 公式：lcm(a, b) = a * b // gcd(a, b)。
• 应用：求多数的公共周期（如蚂蚁碰撞问题）。
5. 模运算与同余
• 费马小定理（Fermat’s Little Theorem）
• 定理：若 p 是素数，且 a 不被 p 整除，则 a^(p-1) ≡ 1 (mod p)。
• 应用：快速计算模逆元（当 p 是素数时，a^{-1} ≡ a^{p-2} (mod p)）。
• 欧拉定理
• 定理：若 a 与 n 互质，则 a^φ(n) ≡ 1 (mod n)（φ(n) 为欧拉函数）。
• 应用：广义模逆元计算、RSA加密。
• 快速幂算法（Binary Exponentiation）
• 定理：通过二进制分解指数，快速计算 a^b mod m。
• 代码片段：
def pow_mod(a, b, m):
result = 1
a = a % m
while b > 0:
if b % 2 == 1:
result = (result * a) % m
a = (a * a) % m
b = b // 2
return result
• 应用：大数取模、离散对数问题。
竞赛高频题型与技巧
素数相关
• 区间筛法（如 [L, R] 内素数统计）。
• 分解质因数优化（预处理素数表后试除法）。
GCD/LCM相关
• 多数的最大公因数/最小公倍数（迭代计算）。
• 构造数组使得 gcd 或 lcm 满足特定条件。
同余方程
• 中国剩余定理（CRT）解线性同余方程组。
• 扩展欧几里得解不定方程。
数论函数
• 欧拉函数 φ(n) 的计算（利用质因数分解）。
• 约数函数（如 σ(n) 表示约数和）。
总结
编程竞赛中，数论问题的核心是 快速实现数学定理的算法化，例如：
• 用 筛法 预处理素数表，
• 用 欧几里得算法 求 GCD 和逆元，
• 用 快速幂 处理大指数取模，
• 用 扩展欧几里得 解方程。
关键技巧：结合数学性质（如奇偶性、质因数分解）和位运算/递归优化代码效率。