《算法竞赛中的初等数论》精讲：从零到精通的十五万字实战指南

1. 初等数论在算法竞赛中的核心地位

第一次参加ACM区域赛时，我遇到这样一道题：给定n个整数，求有多少对(i,j)满足a_i和a_j互质。当时对欧拉函数一知半解的我，只能暴力枚举所有组合，结果自然是TLE。这次惨痛教训让我明白，数论不是可有可无的选修课，而是算法竞赛选手的必修内功。

数论研究整数的性质，就像乐高积木的基础模块。整除理论是搭建所有复杂结构的砖块，同余理论则是连接这些砖块的粘合剂。在ACM/ICPC中，约60%的数学相关题目都涉及这两个基础概念。比如2021年ICPC亚洲区域赛的压轴题，本质就是考察扩展欧几里得算法在模线性方程中的应用。

为什么OI选手要特别重视数论？三个关键原因：

• 时间复杂度降维打击：用筛法预处理素数能在O(1)时间判断质数，而暴力算法需要O(√n)
• 问题转化利器：中国剩余定理能将复杂同余方程组转化为简单形式
• 思维简化工具：欧拉定理可以大幅简化模幂运算的计算量

我建议新手从这三个方向切入：

1. 整除性判定：掌握快速判断约数、倍数的技巧
2. 素数处理：熟练使用埃拉托斯特尼筛法和线性筛
3. 模运算本质：理解同余式的等价变形原理

2. 基础数论工具包构建指南

2.1 快速幂算法：从入门到精通

遇到计算3^100 mod 7这类问题时，新手常犯的错误是直接计算大数再取模。实际上，利用快速幂算法可以在O(log n)时间内解决：

def qpow(a, b, mod): res = 1 while b: if b & 1: res = res * a % mod a = a * a % mod b >>= 1 return res

这个算法的精妙之处在于将指数二进制分解。以3^5为例：

• 5的二进制是101
• 3^5 = 3^(4+1) = 3^4 * 3^1
• 通过平方操作快速构建3^1, 3^2, 3^4...

在2020年NOI的一道题目中，需要计算(2^n + 3^n) mod 1e9+7。直接计算显然会溢出，但用快速幂配合模运算性质：(a+b) mod m = (a mod m + b mod m) mod m，就能高效求解。

2.2 欧几里得算法进阶之路

gcd算法看似简单，但很多选手直到省赛还不会写非递归版本。标准的辗转相除实现：

def gcd(a, b): return a if b == 0 else gcd(b, a % b)

但在处理大数时，递归可能导致栈溢出。这是我用非递归优化后的版本：

def gcd(a, b): while b: a, b = b, a % b return a

更实用的场景是解线性同余方程ax ≡ c (mod m)。通过扩展欧几里得算法求出特解后，所有解可表示为x = x0 + k*(m/d)，其中d=gcd(a,m)。这在密码学题目中经常出现。

3. 素数处理的工程化思维

3.1 筛法性能对比实测

埃氏筛法是最容易理解的素数筛选算法：

def eratosthenes(n): is_prime = [True] * (n+1) 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 in range(2,n+1) if is_prime[i]]

但当n=1e7时，埃氏筛的缓存命中率会明显下降。欧拉筛（线性筛）通过每个合数只被标记一次，性能提升显著：

def euler_sieve(n): primes = [] is_prime = [True] * (n+1) for i in range(2, n+1): if is_prime[i]: primes.append(i) for p in primes: if i*p > n: break is_prime[i*p] = False if i % p == 0: break return primes

实测数据对比（单位：ms）：

3.2 素数判定的Miller-Rabin算法

面对"判断2^82589933-1是否为素数"这种问题时，传统方法束手无策。Miller-Rabin概率性检测算法却能高效处理：

def is_prime(n, k=5): if n < 2: return False for p in [2,3,5,7,11,13,17,19,23,29]: if n % p == 0: return n == p d = n - 1 s = 0 while d % 2 == 0: d //= 2 s += 1 for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]: if a >= n: continue x = pow(a, d, n) if x == 1 or x == n - 1: continue for _ in range(s - 1): x = pow(x, 2, n) if x == n - 1: break else: return False return True

这个算法的关键在于利用费马小定理和二次探测定理。虽然存在误判概率，但通过增加检测轮数k，可以将错误率降至4^-k以下。

4. 同余理论实战技巧

4.1 中国剩余定理的工程实现

解同余方程组： x ≡ 2 mod 3 x ≡ 3 mod 5 x ≡ 2 mod 7

传统解法需要反复代入计算，而CRT给出了通解公式：

def crt(a_list, m_list): M = 1 for m in m_list: M *= m x = 0 for a, m in zip(a_list, m_list): Mi = M // m x += a * Mi * pow(Mi, -1, m) return x % M

在2019年ICPC亚洲区网络赛中，有一道需要合并20个同余方程的题目。使用普通方法会导致代码超长，而CRT实现仅需10行左右，且时间复杂度仅为O(n log M)。

4.2 离散对数问题的BSGS算法

求解a^x ≡ b (mod p)这类问题，Baby-Step Giant-Step算法将时间复杂度从O(p)优化到O(√p)：

def bsgs(a, b, p): step = int(p**0.5) + 1 table = {} curr = 1 for q in range(step): table[curr] = q curr = curr * a % p giant = pow(a, step * (p - 2), p) curr = b for r in range(step): if curr in table: return r * step + table[curr] curr = curr * giant % p return -1

算法分为两个阶段：

1. Baby-Step：预处理a^0到a^(m-1) mod p，存入哈希表
2. Giant-Step：枚举j，检查b*(a^(-m))^j是否在表中

这个算法在ElGamal加密系统相关的竞赛题目中经常出现，是密码学方向选手必须掌握的技能。

5. 积性函数与筛法优化

5.1 线性筛求欧拉函数

欧拉函数φ(n)的计算如果直接使用定义式，效率极低。利用线性筛可以在O(n)时间内预处理：

def euler_phi_table(n): phi = list(range(n+1)) is_prime = [True]*(n+1) for i in range(2, n+1): if is_prime[i]: for j in range(i, n+1, i): is_prime[j] = False if j != i else is_prime[j] phi[j] -= phi[j] // i return phi

这个实现的关键点在于：

• 初始化phi[i]=i
• 遇到质因数p时，phi[n] -= phi[n]//p
• 确保每个数只被最小质因数处理

在需要频繁查询欧拉函数的题目中，预处理表比实时计算能提升100倍以上的性能。

5.2 莫比乌斯反演实战

解决"求满足1≤a≤n, 1≤b≤m且gcd(a,b)=k的数对数量"这类问题，莫比乌斯反演能化繁为简：

def mobius(n): mu = [1]*(n+1) is_prime = [True]*(n+1) for i in range(2, n+1): if is_prime[i]: for j in range(i, n+1, i): is_prime[j] = False if j != i else is_prime[j] mu[j] *= -1 j = i*i for k in range(j, n+1, j): mu[k] = 0 return mu

应用莫比乌斯反演后，原问题转化为： ∑_{d=1}^{n/k} μ(d)⌊n/(kd)⌋⌊m/(kd)⌋

这种技巧在2018年ICPC世界总决赛的Problem J中就有典型应用，能将O(n^2)暴力算法优化到O(n)级别。