Skip to content

WARNING

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

algo15 数论与组合数学 — demo.py 代码详解 ​

Download demo.py

运行方式 ​

bash
cd docs/algorithms/topics/number-theory/code
python demo.py

代码逐段详解 ​

第1步:二进制快速幂 ​

python
def fast_pow(x, n, mod):
    result = 1
    x = x % mod
    while n > 0:
        if n & 1:
            result = (result * x) % mod
        x = (x * x) % mod
        n >>= 1
    return result

原理:将指数 n 写成二进制。例如 n=13=11012,则 x13=x8⋅x4⋅x1。算法通过不断平方 x 来获得 x2,x4,x8,…,并在二进制位为 1 时乘入结果。

运算步骤(213):

n (binary)n&1resultx
1101124
1100216
11132256
118192—

Result = 8192 = 213。

第2步:矩阵快速幂求斐波那契 ​

python
A = [[1, 1], [1, 0]]
An = mat_pow(A, n - 1, mod)
F_n = An[0][0]

矩阵形式的斐波那契:

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

矩阵快速幂在 O(log⁡n) 时间内完成,比递推 O(n) 快得多。对于 n=1018 级别的查询,这是标准做法。

第3步:欧拉线性筛 ​

python
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  # ← 关键行

关键行的含义:当 i % p == 0 时,p 是 i 的最小质因子。那么 i * p 的最小质因子也是 p。如果继续用更大的质数 p_next 筛 i * p_next,那么 i * p_next 的最小质因子还是 p(因为 p 整除 i),但 p_next > p,这就不是用最小质因子筛了——会造成重复。

举例:i=6, p=2 时 6%2==0,筛掉 12 后 break。如果用 p=3 继续筛,6*3=18 的最小质因子是 2(18=2*9),用 3 筛是重复的。实际上 18 会在 i=9, p=2 时被正确筛掉。

第4步:中国剩余定理 ​

x=∑iai⋅Mi⋅(Mi−1modmi)modM

其中 M=∏mi,Mi=M/mi。

示例:x≡2(mod3),x≡3(mod5),x≡2(mod7):

  • M=105, M1=35,M2=21,M3=15
  • 35−1mod3=2, 21−1mod5=1, 15−1mod7=1
  • x=2⋅35⋅2+3⋅21⋅1+2⋅15⋅1=140+63+30=233≡23(mod105)

第5步:组合数 O(1) 查询 ​

预处理阶乘 fact[n] 和逆阶乘 inv_fact[n]:

python
nCr(n, r) = fact[n] * inv_fact[r] % mod * inv_fact[n-r] % mod

逆阶乘的计算方法:先求 inv_fact[n] = mod_inverse_fermat(fact[n], mod),然后从后往前递推:inv_fact[i-1] = inv_fact[i] * i % mod。

关键概念速查表 ​

概念公式/方法代码位置
快速幂二进制分解fast_pow()
费马逆元amod−2mod_inverse_fermat()
扩展欧几里得ax+by=gcd(a,b)ext_gcd()
矩阵快速幂Fib = [[1,1],[1,0]]^nfibonacci_mat()
埃筛i2 开始标记sieve_eratosthenes()
线性筛最小质因子 breaklinear_sieve()
CRT∑aiMiMi−1crt()
组合数n!/(k!(n−k)!)nCr()
错位排列Dn=(n−1)(Dn−1+Dn−2)derangement()

源码位置 ​

clone 后打开(相对仓库根目录):

docs/algorithms/topics/number-theory/code/demo.py