1. 初等数论在算法竞赛中的核心地位第一次参加ACM区域赛时我遇到这样一道题给定n个整数求有多少对(i,j)满足a_i和a_j互质。当时对欧拉函数一知半解的我只能暴力枚举所有组合结果自然是TLE。这次惨痛教训让我明白数论不是可有可无的选修课而是算法竞赛选手的必修内功。数论研究整数的性质就像乐高积木的基础模块。整除理论是搭建所有复杂结构的砖块同余理论则是连接这些砖块的粘合剂。在ACM/ICPC中约60%的数学相关题目都涉及这两个基础概念。比如2021年ICPC亚洲区域赛的压轴题本质就是考察扩展欧几里得算法在模线性方程中的应用。为什么OI选手要特别重视数论三个关键原因时间复杂度降维打击用筛法预处理素数能在O(1)时间判断质数而暴力算法需要O(√n)问题转化利器中国剩余定理能将复杂同余方程组转化为简单形式思维简化工具欧拉定理可以大幅简化模幂运算的计算量我建议新手从这三个方向切入整除性判定掌握快速判断约数、倍数的技巧素数处理熟练使用埃拉托斯特尼筛法和线性筛模运算本质理解同余式的等价变形原理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的二进制是1013^5 3^(41) 3^4 * 3^1通过平方操作快速构建3^1, 3^2, 3^4...在2020年NOI的一道题目中需要计算(2^n 3^n) mod 1e97。直接计算显然会溢出但用快速幂配合模运算性质(ab) 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)其中dgcd(a,m)。这在密码学题目中经常出现。3. 素数处理的工程化思维3.1 筛法性能对比实测埃氏筛法是最容易理解的素数筛选算法def eratosthenes(n): is_prime [True] * (n1) for i in range(2, int(n**0.5)1): if is_prime[i]: for j in range(i*i, n1, i): is_prime[j] False return [i for i in range(2,n1) if is_prime[i]]但当n1e7时埃氏筛的缓存命中率会明显下降。欧拉筛线性筛通过每个合数只被标记一次性能提升显著def euler_sieve(n): primes [] is_prime [True] * (n1) for i in range(2, n1): 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算法类型n1e6n1e7n1e8埃氏筛120140016000欧拉筛8090095003.2 素数判定的Miller-Rabin算法面对判断2^82589933-1是否为素数这种问题时传统方法束手无策。Miller-Rabin概率性检测算法却能高效处理def is_prime(n, k5): 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算法分为两个阶段Baby-Step预处理a^0到a^(m-1) mod p存入哈希表Giant-Step枚举j检查b*(a^(-m))^j是否在表中这个算法在ElGamal加密系统相关的竞赛题目中经常出现是密码学方向选手必须掌握的技能。5. 积性函数与筛法优化5.1 线性筛求欧拉函数欧拉函数φ(n)的计算如果直接使用定义式效率极低。利用线性筛可以在O(n)时间内预处理def euler_phi_table(n): phi list(range(n1)) is_prime [True]*(n1) for i in range(2, n1): if is_prime[i]: for j in range(i, n1, 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]*(n1) is_prime [True]*(n1) for i in range(2, n1): if is_prime[i]: for j in range(i, n1, i): is_prime[j] False if j ! i else is_prime[j] mu[j] * -1 j i*i for k in range(j, n1, j): mu[k] 0 return mu应用莫比乌斯反演后原问题转化为 ∑_{d1}^{n/k} μ(d)⌊n/(kd)⌋⌊m/(kd)⌋这种技巧在2018年ICPC世界总决赛的Problem J中就有典型应用能将O(n^2)暴力算法优化到O(n)级别。