分享丨【算法题单】数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
灵茶山艾府
88613
2024.05.14
2025.10.16
发布于 浙江
几何数学组合数学博弈数论Java周赛数据结构与算法双周赛概率与统计随机化力扣竞赛学习分享

数学题单数学题目力扣数学题单leetcode数学数论组合博弈几何随机 灵茶山艾府 灵神

图：暴力？NO！数学做法，降维打击！

前言

本文整理了力扣上的数学相关题目，主要以数论和组合数学为主。

部分题目（尤其是组合数学）会涉及到取模，我写了一篇教程，请看 模运算的世界：当加减乘除遇上取模。

一、数论

§1.1 判断质数

模板：

Python3
Java
C++
Go
# 时间复杂度 O(sqrt(n))
def is_prime(n: int) -> bool:
    for i in range(2, isqrt(n) + 1):
        if n % i == 0:
            return False
    return n >= 2  # 1 不是质数

更快的模板（写法二）

§1.2 预处理质数（筛质数）

模板（埃氏筛）：

Python3
Java
C++
Go
# 时间复杂度 O(MX * log log MX)
MX = 1_000_001
is_prime = [False] * 2 + [True] * (MX - 2)  # 0 和 1 不是质数
primes = []
for i in range(2, MX):
    if is_prime[i]:
        primes.append(i)
        for j in range(i * i, MX, i):
            is_prime[j] = False  # j 是质数 i 的倍数

§1.3 质因数分解

模板一，预处理每个数的所有不同质因子。原理同埃氏筛。

Python3
Java
C++
Go
MX = 1_000_001
prime_factors = [[] for _ in range(MX)]
for i in range(2, MX):
    if not prime_factors[i]:  # i 是质数
        for j in range(i, MX, i):  # i 的倍数 j 有质因子 i
            prime_factors[j].append(i)

模板二，预处理 的最小质因子 ，从而做到 分解 。可以求出 的每个质因子的个数。

Python3
Java
C++
Go
MX = 1_000_001
lpf = [0] * MX
for i in range(2, MX):
    if lpf[i] == 0:  # i 是质数
        for j in range(i, MX, i):
            if lpf[j] == 0:  # 首次访问 j
                lpf[j] = i

# 质因数分解
# 例如 prime_factorization(45) = [(3, 2), (5, 1)]，表示 45 = 3**2 * 5**1
# 时间复杂度 O(log x)
def prime_factorization(x: int) -> List[Tuple[int, int]]:
    res = []
    while x > 1:
        p = lpf[x]
        e = 1
        x //= p
        while x % p == 0:
            e += 1
            x //= p
        res.append((p, e))
    return res

§1.4 阶乘分解

§1.5 因子

模板（预处理每个数的所有因子）：

Python3
Java
C++
Go
# 预处理每个数的因子
MX = 1_000_001  # **根据题目调整**
divisors = [[] for _ in range(MX)]
for i in range(1, MX):
    for j in range(i, MX, i):  # 枚举 i 的倍数 j
        divisors[j].append(i)  # i 是 j 的因子

§1.6 最大公约数（GCD）

部分语言的标准库没有 GCD 和 LCM，需要手写。推荐写迭代，比递归快一点。

Java
Go
class Solution {
    private long gcd(long a, long b) {
        while (a != 0) {
            long tmp = a;
            a = b % a;
            b = tmp;
        }
        return b;
    }

    // 推荐先除后乘，尽量避免溢出
    private long lcm(long a, long b) {
        return a / gcd(a, b) * b;
    }
}

§1.7 最小公倍数（LCM）

§1.8 互质

§1.9 同余

§1.10 其他

二、组合数学

快速幂、组合数的预处理模板见 模运算的世界：当加减乘除遇上取模

§2.1 乘法原理

§2.2 组合计数

关于生成函数的题目，见本题单的「§2.6 生成函数」。

§2.3 放球问题

图解：多重集组合数

思维扩展：

  • 3669. K 因数分解 这题不是组合数学题，但分析算法的计算量需要用到组合数学

§2.4 容斥原理

部分题目有其他解法，难度分仅供参考。

§2.5 贡献法

思维扩展：

§2.6 生成函数（母函数）

三、概率期望

随机数据下显著更快的算法：

四、博弈论

五、计算几何

§5.1 点、线

§5.2 圆

§5.3 矩形、多边形

§5.4 凸包

另见 动态规划题单 的「§11.7 斜率优化 DP」。

六、随机算法

§6.1 随机数

§6.2 随机化技巧

七、杂项

§7.1 回文数

从小到大枚举回文数的模板（从 开始枚举）：

Python3
Java
C++
Go
def gen_palindrome() -> Iterator[int]:
    base = 1
    while True:
        # 生成奇数长度回文数，例如 base = 10，生成的范围是 101 ~ 999
        for i in range(base, base * 10):
            s = str(i)
            x = int(s + s[::-1][1:])
            yield x

        # 生成偶数长度回文数，例如 base = 10，生成的范围是 1001 ~ 9999
        for i in range(base, base * 10):
            s = str(i)
            x = int(s + s[::-1])
            yield x

        base *= 10


for x in gen_palindrome():
    if x > 10 ** 9:  # 根据题目调整
        break
    # 处理 x 的逻辑写下面
    print(x)

§7.2 整数拆分

§7.3 曼哈顿距离

§7.4 多项式

另见本题单的「§2.6 生成函数」。

§7.5 快速沃尔什变换（FWT）

§7.6 线性基

见 位运算题单。

§7.7 其他

算法题单

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
  7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

如果你发现有题目可以补充进来，欢迎评论反馈。

评论 (72)