数学算法

数学题真正考的通常不是公式记忆，而是识别结构：能不能取模，能不能拆成递推，能不能把组合数转成预处理。

核心方向

数论基础

• 质数判断与筛法 - 试除法、埃氏筛、欧拉筛
• GCD与LCM - 欧几里得算法、扩展GCD、逆元
• 扩展欧几里得与模逆元 - 求系数、逆元和线性同余
• 同余与模运算 - 为什么可以取模、什么时候能做“除法”

快速幂与矩阵

• 快速幂算法 - 整数快速幂、矩阵快速幂、大数取模

组合数学

• 排列组合 - 排列数、组合数、杨辉三角、康托展开
• 组合数取模与Lucas定理 - 大组合数在质数模下的求法
• 卡特兰数 - 合法括号、BST 结构数

经典数列

• 斐波那契数列 - 5种求解方法、黄金分割、经典应用

怎么识别数学题

看到下面这些信号，通常就要往数学方向想：

1. 题目出现大数、取模、整除、倍数、质数。
2. 有明显递推，但 n 非常大。
3. 结果本质上是在计数。
4. 暴力枚举组合明显超时。

高频工具

数论基础

• 质数判断
• 筛法
• gcd / lcm
• 模运算与逆元

快速幂技巧

• 二进制拆分
• 每步取模防溢出
• 矩阵快速幂加速线性递推

组合数学

• 排列组合
• 组合数递推
• Lucas 定理
• 卡特兰数

经典数列

• 斐波那契
• 卡特兰数
• 递推转矩阵

一张表看常见做法

学习顺序

1. 先学 GCD 与 LCM、同余与模运算。
2. 再学 快速幂，这是最常用的数学模板之一。
3. 然后补 组合数取模 和 卡特兰数。
4. 最后回过头看递推数列和矩阵加速。

易错点

数学题常见错误不是公式不会，而是适用条件没看清。

• 取模意义下不能随便做除法，除非先转成逆元。
• Lucas 定理和费马小定理都有模数条件。
• 快速幂里每一步都要及时取模。
• 组合数题要先分清是排列还是组合，顺序是否重要。

相关主题

• 算法模板
• 动态规划
• 搜索算法
• 扩展欧几里得与模逆元
• 同余与模运算

返回：算法学习导航