programming-notes

ACM-ICPC / OI 常考知识点体系整理

一、数学基础（数论 / Number Theory）

这是你刚刚那题所属模块。

1. 因子与约数

• 因子个数公式
• 完全平方数 → 因子个数为奇数
• 枚举/分解优化到 √n

2. 质数

• 质数判断（O(√n)）
• 埃氏筛
• 线性筛（欧拉筛）

3. 最大公约数 / 最小公倍数

• gcd（辗转相除法）
• lcm(a,b)=a*b/gcd(a,b)

4. 同余与取模

• (a+b)%p
• 快速幂
• 模逆元（费马小定理）

5. 快速幂

• O(log n)
• 二进制思想

---

二、数据结构

1. 数组 / 模拟

• 前缀和
• 差分数组

2. 栈与队列

• 单调栈（Next Greater Element）
• 单调队列（滑动窗口最值）

3. 哈希

• HashMap / HashSet
• 字符串哈希（滚动哈希）

4. 堆

• 优先队列
• TopK问题

5. 并查集（Union Find）

• 连通性问题
• 路径压缩

6. 树状数组（BIT）

• 单点修改 + 区间查询

7. 线段树

• 区间修改 / 区间查询

---

三、图论

1. 图的存储

• 邻接表
• 邻接矩阵

2. 图遍历

• DFS
• BFS

3. 最短路

• Dijkstra
• Bellman-Ford
• Floyd

4. 最小生成树

• Kruskal
• Prim

5. 拓扑排序

• DAG排序

6. 强连通分量

• Tarjan算法

---

四、动态规划（DP）

1. 线性DP

• 最长递增子序列 LIS
• 最大子段和

2. 背包问题

• 01背包
• 完全背包
• 多重背包

3. 区间DP

• 矩阵链乘
• 回文问题

4. 状态压缩DP

• TSP问题

---

五、贪心算法

• 区间调度
• 排序 + 选择策略
• Huffman编码

---

六、字符串算法

1. 基础字符串

• KMP
• next数组

2. Trie树

• 字典树

3. 字符串哈希

• 快速比较

---

七、搜索

1. DFS

• 回溯

2. BFS

• 最短路径（无权图）

3. A*

• 启发式搜索

---

八、基础算法思想

• 分治
• 二分答案
• 双指针
• 前缀思想

---

九、常见题型分类

• 数论基础题（如你这题）
• 排序+贪心
• 图最短路
• DP最优解
• 区间维护问题

---

总结

👉 你刚才那道题属于： > 数论 - 因子性质 - 完全平方数问题

This site is open source. Improve this page.