Skip to content

algo15 数论与组合数学 ​

WARNING

🧪 Beta公测版本提示:教程主体已完成,正在优化细节,欢迎大家提Issue反馈问题或建议。

模运算、素数筛、快速幂、最大公约数、组合数取模——算法竞赛中的数学工具箱


一、模运算(Modular Arithmetic) ​

1.1 基本运算 ​

在模 M 意义下,所有运算结果都取模:

(a+b)modM=((amodM)+(bmodM))modM(a−b)modM=((amodM)−(bmodM)+M)modM(a×b)modM=((amodM)×(bmodM))modM

除法需要特殊处理——用模逆元代替除法。

1.2 模逆元(Modular Inverse) ​

a 在模 M 下的乘法逆元 a−1 满足 a⋅a−1≡1(modM)。逆元存在的充要条件是 gcd(a,M)=1。

三种求法:

方法条件复杂度
费马小定理M 为质数O(log⁡M)
扩展欧几里得任意 M(只要 gcd(a,M)=1)O(log⁡min(a,M))
线性递推批量求 1 到 n 的所有逆元O(n)

费马小定理(M 为质数):

a−1≡aM−2(modM)

证明:aM−1≡1(modM)(费马小定理),两边同乘 a−1。

逐步推导:快速幂 anmodM,以及 gcd 与逆元(点击展开)

n 的二进制:n=∑bk2k。维护 p←a2k,若 bk=1 则乘进答案。O(log⁡n) 次模乘。费马:M 质数、a≢0,则 aM−2≡a−1。

欧几里得:gcd(a,b)=gcd(b,amodb)。扩展欧几里得找 ax+by=gcd。gcd(a,M)=1 时 ax≡1(modM),x 即逆元。组合数 C(n,k)=n!/(k!(n−k)!) 在模质数下把阶乘逆元打表,O(n) 预处理后 O(1) 查询。

1.3 中国剩余定理(CRT) ​

对于一组同余方程组:

{x≡a1(modm1)x≡a2(modm2)⋯x≡ak(modmk)

其中 mi 两两互质,CRT 给出了在模 M=∏mi 下的唯一解:

x≡∑i=1kai⋅Mi⋅Mi−1(modM)

其中 Mi=M/mi,Mi−1 是 Mi 在模 mi 下的逆元。


二、快速幂与矩阵快速幂 ​

2.1 二进制快速幂(Binary Exponentiation) ​

计算 xnmodM 可在 O(log⁡n) 内完成:

python
def fast_pow(x, n, mod):
    result = 1
    while n > 0:
        if n & 1:               # 当前二进制位为 1
            result = result * x % mod
        x = x * x % mod         # 平方
        n >>= 1                 # 右移一位
    return result

原理:将指数 n 分解为二进制 n=∑bi⋅2i,则 xn=∏xbi⋅2i,而 x2i 可以通过不断平方得到。

2.2 矩阵快速幂 ​

快速幂的思想可以推广到矩阵。矩阵乘法的结合律使得 An 也能在 O(k3log⁡n) 内计算(k 是矩阵维度)。

经典应用:斐波那契数列第 n 项:

[FnFn−1]=[1110]n−1[F1F0]

三、素数筛法 ​

3.1 埃拉托色尼筛(Sieve of Eratosthenes) ​

筛选出 1 到 n 中的所有素数。核心思想:从 2 开始,将每个素数的所有倍数标记为合数。

python
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):  # 从 i*i 开始,更小的已被筛过
                is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

复杂度:O(nlog⁡log⁡n)。虽然每个合数可能被多个素数标记,但总次数近似为调和级数。

3.2 欧拉线性筛(Euler's Linear Sieve) ​

保证每个合数只被其最小质因子筛掉一次,达到 O(n):

python
def linear_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

关键行 if i % p == 0: break:当 p 是 i 的最小质因子时,i⋅p 的最小质因子就是 p。继续用更大的 p 筛 i⋅p 会用非最小质因子筛除——重复了。


四、最大公约数与扩展欧几里得 ​

4.1 欧几里得算法(辗转相除法) ​

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

复杂度:O(log⁡min(a,b))。

4.2 扩展欧几里得算法 ​

求解 ax+by=gcd(a,b) 的一组整数解 (x,y):

python
def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0  # gcd, x, y
    g, x1, y1 = ext_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return g, x, y

应用:求模逆元——解 ax+My=1 即可得 a−1≡x(modM)。


五、组合数学基础 ​

5.1 排列与组合 ​

  • 排列 P(n,k)=n!(n−k)!:有序选取 k 个
  • 组合 C(n,k)=(nk)=n!k!(n−k)!:无序选取 k 个

5.2 二项式系数计算 ​

方法一:递推(Pascal's Triangle)

(nk)=(n−1k−1)+(n−1k)

适用于 n≤2000,预处理 O(n2),查询 O(1)。

方法二:组合数公式 + 模逆元

(nk)=n!k!(n−k)!modM

预处理阶乘和逆阶乘,O(n) 预处理,O(1) 查询。需要 M 为质数。

5.3 容斥原理 ​

|⋃i=1nAi|=∑i|Ai|−∑i<j|Ai∩Aj|+∑i<j<k|Ai∩Aj∩Ak|−⋯+(−1)n+1|A1∩⋯∩An|

经典应用:

  • 1 到 n 中与 m 互质的数的个数
  • 错位排列(Derangements)

5.4 错位排列 ​

n 个元素的排列中,没有元素出现在原位的排列数 Dn:

Dn=n!∑k=0n(−1)kk!

递推:D1=0,D2=1,Dn=(n−1)(Dn−1+Dn−2)。

素数筛法对比图:左侧展示埃拉托色尼筛的动画——从2开始,逐步标记4,6,8...为合数,用不同颜色高亮;右侧展示欧拉线性筛的工作过程——表格列出每个数i和当前素数列表,标注每次被筛掉的合数及其最小质因子


六、概率基础 ​

6.1 期望的线性性 ​

线性性质:对于任意随机变量 X1,X2,…,Xn(即使不独立),都有:

E[∑i=1nXi]=∑i=1nE[Xi]

这是概率论中最强大也最常用的性质之一。它允许将复杂期望分解为简单期望的和。

经典应用:掷 n 个骰子,期望有几个 6?每个骰子出 6 的期望是 1/6,n 个骰子期望有 n/6 个 6。


本章总结 ​

概念公式/方法复杂度
模运算加减乘直接取模O(1)
模逆元(费马)a−1≡aM−2O(log⁡M)
中国剩余定理x≡∑aiMiMi−1O(klog⁡M)
快速幂二进制分解O(log⁡n)
埃筛标记倍数O(nlog⁡log⁡n)
线性筛最小质因子O(n)
欧几里得gcd(a,b)=gcd(b,a%b)O(log⁡min(a,b))
扩展欧几里得ax+by=gcd(a,b)O(log⁡min(a,b))
组合数阶乘+逆元 或 Pascal 递推O(1)/O(n2)
容斥原理交集和并集转换取决于项数
期望线性性E[∑Xi]=∑E[Xi]—

📥 Code ​

FileViewDownload
demo.pyOpenDownload
exercise.pyOpenDownload

参考 ​

  1. Hardy, G. H. & Wright, E. M. (1979). An Introduction to the Theory of Numbers (5th ed.). Oxford University Press.
  2. Knuth, D. E. (1997). The Art of Computer Programming, Vol. 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley.
  3. Euler, L. (1748). Introductio in analysin infinitorum. (线性筛以欧拉命名)