前言 信息学竞赛中的数学知识
0.1 大纲要求
入门级：
提高级：
NOI级：
0.2 信息学竞赛中的数论和数学竞赛有什么区别？
-
入门阶段，不重视对具体概念的辨析（例如，数学竞赛的入门数论题要求证明某个式子被另一个式子整除），重视算法模板的实现；
-
高阶竞赛中更重视一些“不那么优雅”的技巧。
-
数学竞赛的数论问题，最后的结论往往是直接的，或者说，\(O(1)\)的；
-
信息学竞赛中的数论题，往往会设计“刚刚好”的数据范围，卡在某个复杂度上，如 \(O(n^{\frac{3}{2}})\)、\(O(n^{\frac{2}{3}})\)，\(O(n^{\frac{3}{4}})\)这些很丑陋的形式。
-
本质上，信息学竞赛中的数论就是在认识数学语言后，容斥、分块，前期注重概念，后期运用各种技巧。
-
其实其它数学问题也一样，只需要知道那些语言是什么意思就行，后续的分析大部分要靠各种经验总结、常用思想。
0.3 课程安排
5天
- 27日上午：第一部分（数论基本概念、最大公约数）
- 27日下午：洛谷月赛
- 28日上午：第一部分（数论基本概念、最大公约数）
- 28日下午、29日全天：第二部分（几个重要定理、数论函数、重要算法模板）
- 30日全天：第三部分（数论分块、数论求和）
- 31日上午：模拟赛
- 31日下午：补题、总结
一、数论基本概念
- 自然数、整数
- 加减乘除
- 带余数除法
- 整除
- 因数与倍数
- 质数与合数
1.1 质数的筛法
埃氏筛法
线性筛法