第11章：数学与数论
数学是算法的基石。在算法竞赛中，总有一些题目在“暴力”的外衣下，隐藏着一个数学或数论的内核。能否看穿这一点，并用高效的工具解决它，往往是区分“暴力选手”和“技巧选手”的关键。本章将聚焦于竞赛中最常遇到的数论与数学问题，并展示Python如何利用其丰富的标准库和语言特性，将复杂的数学计算“降维打击”为几行优雅的代码。
11.1 质数与约数：筛法、math.gcd, math.lcm
质数和约数是数论问题的起点，几乎贯穿了数论的全领域。
1. 质数 (Prime Number)
质数，又称素数，是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
判断单个质数：试除法
最直观的方法是试除法：检查从2到 Nsqrt{N}N
的所有整数能否整除 NNN。如果都不能，那么 NNN 就是质数。这个方法的时间复杂度为 O(N)O(sqrt{N})O(N
)，适用于 NNN 比较大但判断次数不多的情况。
import math
def is_prime(n: int) -> bool:
"""判断一个数是否为质数"""
if n < 2:
return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
# 示例
print(f"13 is prime: {
is_prime(13)}") # True
print(f"20 is prime: {
is_prime(20)}") # False
批量生成质数：埃氏筛 (Sieve of Eratosthenes)
当需要找出一定范围（例如 111 到 10610^6106）内所有质数时，O(N)O(sqrt{N})O(N
) 的试除法会超时。此时，更高效的策略是“筛法”。埃氏筛是其中最经典、最常用的算法。
其思想是：从2开始，将每个质数的倍数都标记为合数。一个数如果没有被前面的质数标记过，那它一定是质数。
def prime_sieve(n: int) -> list[bool]:
"""
埃氏筛法，返回一个布尔列表，is_prime[i]为True表示i是质数。
时间复杂度: O(N log log N)
"""
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False # 0和1不是质数
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
# i的倍数(从i*i开始)都不是质数
for j in range(i * i, n + 1, i):
is_prime[j] = False
return is_prime
# 找出100以内的所有质数
limit = 100
primes_bool = prime_sieve(limit)
prime_numbers = [i for i, is_p in enumerate(primes_bool) if is_p]
print(f"Primes up to {
limit}: {
prime_numbers}")
# 输出: Primes up to 100: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
埃氏筛的代码简洁，效率极高，足以应对绝大多数竞赛场景。
2. 约数 (Divisor)
最大公约数 (GCD) 和 最小公倍数 (LCM)
在C++中，你可能需要自己手写欧几里得算法（辗转相除法）来求GCD。但在Python中，这完全是降维打击。math库已经为我们提供了现成、高效的函数。
math.gcd(a, b): 计算a和b的最大公约数。
math.lcm(a, b): 计算a和b的最小公倍数 (Python 3.9+)。
import math
a, b = 48, 18
# 最大公约数
gcd_val = math.gcd(a, b)
print(f"GCD of {
a} and {
b} is {
gcd_val}") # 6
# 最小公倍数
# 对于 Python 3.9+
if hasattr(math, 'lcm'):
lcm_val = math.lcm(a, b)
else:
# 对于老版本Python，使用公式 (a * b) // gcd(a, b)
lcm_val = (a * b) // math.gcd(a, b)
print(f"LCM of {
a} and {
b} is {
lcm_val}") # 144
实战铁律： 永远使用math.gcd()，不要自己实现。对于多个数的GCD，math.gcd(a, math.gcd(b, c))即可。
11.2 模运算与快速幂：pow(a, b, m)的妙用
很多算法题目的结果会非常大，常常会要求将结果对一个大数（如 109+710^9+7109+7）取模。
模运算 (Modular Arithmetic)
模运算就是取余数，在Python中用 % 运算符。它满足一些基本性质：
(a+b)(modm)=((a(modm))+(b(modm)))(modm)(a + b) pmod m = ((a pmod m) + (b pmod m)) pmod m(a+b)(modm)=((a(modm))+(b(modm)))(modm)
(a−b)(modm)=((a(modm))−(b(modm))+m)(modm)(a – b) pmod m = ((a pmod m) – (b pmod m) + m) pmod m(a−b)(modm)=((a(modm))−(b(modm))+m)(modm)
(a×b)(modm)=((a(modm))×(b(modm)))(modm)(a imes b) pmod m = ((a pmod m) imes (b pmod m)) pmod m(a×b)(modm)=((a(modm))×(b(modm)))(modm)
这意味着在计算过程中可以随时取模，防止中间结果溢出。
快速幂 (Fast Powering)
一个核心问题是计算 (ab)(modm)(a^b) pmod m(ab)(modm)。当 bbb 巨大时（例如 101810^{18}1018），直接计算 a ** b 会导致时间和内存的双重溢出。
快速幂算法（也叫二进制取幂）可以高效解决这个问题。它的思想是将指数 bbb 进行二进制拆分，从而将计算 bbb 次乘法的问题转化为计算约 logblog blogb 次乘法。
例如，计算 a13a^{13}a13。因为 131313 的二进制是 1101_21101\_21101_2，所以 13=8+4+113 = 8 + 4 + 113=8+4+1。
因此，a13=a8×a4×a1a^{13} = a^8 imes a^4 imes a^1a13=a8×a4×a1。我们可以通过递推 a1,a2,a4,a8,…a^1, a^2, a^4, a^8, dotsa1,a2,a4,a8,… 快速得到结果。
Python的降维打击：
你不需要手写快速幂！Python的内置函数 pow() 提供了三个参数的版本，其作用就是高效、安全地执行模幂运算。
pow(a, b, m) 的作用就是高效地计算 (ab)(modm)(a^b) pmod m(ab)(modm)。
# 场景：计算 (3^1000000000) % (10^9 + 7)
a = 3
b = 1000000000
m = 10**9 + 7
# 错误且极慢的方式，会导致OverflowError
# result = (a ** b) % m
# 正确、高效、Pythonic的方式
result = pow(a, b, m)
print(f"({
a}^{
b}) % {
m} = {
result}") # 511527313
实战铁律： 在任何需要计算模幂的场景，必须使用 pow(a, b, m)。它不仅代码简洁，而且其底层由C语言实现，速度极快，是Python在算法竞赛中的一大“杀器”。
11.3 组合计数：math.comb, math.perm与预处理组合数
排列组合是计数类问题的常客。
排列数 PnkP_n^kPnk 和 组合数 CnkC_n^kCnk
排列数：从 nnn 个不同元素中取出 kkk 个，考虑顺序。Pnk=n!(n−k)!P_n^k = frac{n!}{(n-k)!}Pnk=(n−k)!n!
组合数：从 nnn 个不同元素中取出 kkk 个，不考虑顺序。Cnk=n!k!(n−k)!C_n^k = frac{n!}{k!(n-k)!}Cnk=k!(n−k)!n!
Python的降维打击：
从Python 3.8开始，math库直接内置了计算排列组合的函数，可以直接处理中等大小的 n,kn, kn,k。
math.perm(n, k): 计算排列数 PnkP_n^kPnk
math.comb(n, k): 计算组合数 CnkC_n^kCnk
import math
n, k = 10, 3
# 计算 P(10, 3)
p_val = math.perm(n, k)
print(f”P({n}, {k}) = {p_val}”) # 720
# 计算 C(10, 3)
c_val = math.comb(n, k)
print(f”C({n}, {k}) = {c_val}”) # 120
“`
对于不需要取模且 $n, k$ 不会大到超时的题目，这两个函数是你的首选，它们再次完美诠释了Python的便利性。
需要取模的组合数：预处理阶乘和逆元
当题目要求计算 Cnk(modm)C_n^k pmod mCnk(modm)（mmm 通常是一个大质数），math.comb 就无能为力了。我们需要利用公式：
Cnk≡(n!×(k!)−1×((n−k)!)−1)(modm)C_n^k equiv left( n! imes (k!)^{-1} imes ((n-k)!)^{-1}
ight) pmod mCnk≡(n!×(k!)−1×((n−k)!)−1)(modm)
这里的 (x)−1(x)^{-1}(x)−1 指的是 xxx 在模 mmm 意义下的乘法逆元。
根据费马小定理，当 mmm 是质数时，am−2≡a−1(modm)a^{m-2} equiv a^{-1} pmod mam−2≡a−1(modm)。这个逆元可以用我们刚刚学到的快速幂 pow(a, m-2, m) 轻松求出。
如果一个题目需要多次查询组合数，最高效的做法是预处理。我们提前计算好一定范围内所有数的阶乘及其模逆元。
# 场景：多次查询 C(n, k) % m 的值，m为质数
MOD = 10**9 + 7
MAX_N = 2000 # 预处理的范围
# 预处理阶乘
fact = [1] * (MAX_N + 1)
for i in range(2, MAX_N + 1):
fact[i] = (fact[i-1] * i) % MOD
# 预处理阶乘的逆元
inv_fact = [1] * (MAX_N + 1)
# 计算 fact[MAX_N] 的逆元，然后递推回去
inv_fact[MAX_N] = pow(fact[MAX_N], MOD - 2, MOD)
for i in range(MAX_N - 1, -1, -1):
inv_fact[i] = (inv_fact[i+1] * (i+1)) % MOD
def combinations_mod(n, k, m):
"""O(1)时间内查询预处理好的组合数"""
if k < 0 or k > n:
return 0
# C(n,k) = n! / (k! * (n-k)!)
numerator = fact[n]
denominator = (inv_fact[k] * inv_fact[n - k]) % m
return (numerator * denominator) % m
# 示例查询
print(f"C(10, 3) % MOD = {
combinations_mod(10, 3, MOD)}") # 120
print(f"C(100, 50) % MOD = {
combinations_mod(100, 50, MOD)}") # 896343183
print(f"C(2000, 1000) % MOD = {
combinations_mod(2000, 1000, MOD)}") # 预处理后可快速得出
这套“预处理阶乘+逆元”的模板是解决模意义下组合计数问题的标准武器，需要熟练掌握。
11.4 浮点数精度问题与Decimal模块
在算法竞赛中，直接使用float类型进行浮点数运算是一件风险很高的事情，因为计算机使用二进制存储小数，无法精确表示所有十进制小数。
# 一个经典的精度问题
val1 = 0.1
val2 = 0.2
print(f"0.1 + 0.2 = {
val1 + val2}") # 输出 0.30000000000000004
print(f"0.1 + 0.2 == 0.3: {
val1 + val2 == 0.3}") # False
这种微小的误差在需要精确比较或累加时是致命的，会导致WA（Wrong Answer）。
处理策略：
尽量转换为整数运算： 如果可能，将所有小数乘以一个共同的倍数（如100，1000），将问题转化为整数域上的问题，这是最安全、最快速的方法。
设定一个极小量eps： 在比较两个浮点数a和b是否相等时，不使用a == b，而是判断它们的差的绝对值是否小于一个极小量epsilon（如1e-7或1e-9）。即 abs(a - b) < eps。
终极武器Decimal模块： 当题目明确要求高精度小数运算时（例如金融计算），Python的Decimal模块就派上了用场。它提供了一种能够精确表示十进制小数的数据类型。
from decimal import Decimal, getcontext
# 设置精度，例如小数点后50位
getcontext().prec = 50
# 注意：必须用字符串来初始化Decimal，否则会从不精确的float转换，失去意义
a = Decimal('0.1')
b = Decimal('0.2')
c = Decimal('0.3')
print(f"Decimal('0.1') + Decimal('0.2') = {
a + b}")
print(f"Is it equal to Decimal('0.3')? {
a + b == c}") # True
# 进行高精度计算
sqrt_2 = Decimal('2').sqrt()
print(f"高精度的sqrt(2): {
sqrt_2}")
使用建议：
Decimal的性能远低于float。因此，它只应该在“不得不”使用高精度计算的场合出现。对于绝大多数题目，优先考虑策略1和策略2。Decimal是你最后的、也是最可靠的保障。
本章小结：
数学与数论是Python的“降维打击”优势区。无论是math.gcd, pow(a, b, m),还是math.comb，Python都将原本需要精心实现的核心算法封装成了即开即用的函数。作为一名Pythonic的竞赛选手，你的任务是洞察问题的数学本质，然后熟练、准确地调用这些强大的工具。对于更复杂的场景，如模意义下的组合数，则需要你掌握“预处理”这一思想，打好模板，以不变应万变。对浮点数保持警惕，熟悉Decimal的用法，能让你在面对精度陷阱时从容不迫。
暂无评论内容