数论

基础数论

基础数论包含了处理整数性质和关系的基本算法。

特点

1. 时间复杂度：从 到 不等
2. 空间复杂度：通常为 或
3. 适用于整数运算、因数分解等场景

分类

质数判定	判断一个数是否为质数
埃氏筛	生成质数表
欧几里得	求最大公约数
扩展欧几里得	求解线性方程

同余运算

同余运算是处理模运算的重要工具。

特点

1. 时间复杂度：与具体运算相关
2. 空间复杂度：通常为
3. 适用于大数运算、密码学等场景

分类

组合数学

组合数学处理计数和排列组合问题。

特点

1. 时间复杂度：通常为 或
2. 空间复杂度：通常为 或
3. 适用于计数、排列、组合等问题

分类

应用场景对比

基础数论适合：

1. 质因数分解
2. 最大公约数
3. 最小公倍数
4. 整数性质判断

同余运算适合：

1. 大数运算
2. 模运算优化
3. 密码学应用
4. 周期性问题

组合数学适合：

1. 计数问题
2. 排列组合
3. 序列生成
4. 集合划分

选择建议

1. 整数性质问题选择基础数论
2. 大数运算问题选择同余运算
3. 计数问题选择组合数学
4. 需要预处理时考虑筛法
5. 需要优化时考虑数论函数