基础数论教学体会

Bellala, 20240910

第一部分：整体思路

OI 数学教学中的两个问题：

如何讲明白一个数学知识点？

如果课堂没有时间限制，怎么让学生彻底理解某个知识点？

应该讲到何种程度？

有些知识点没必要证明，有些知识点需要掌握证明过程，如何把握？

大部分数学知识点可分为四步：

• 动机（motivation）
• 直观（intuition）
• 证明
• 代码

经过以上四部分的讲解，学生应能完全掌握相应的内容。

然而，由于课时限制、学生水平有别，且不同知识点的难度、出现频率不同，故在教学时应有所取舍。

直观

• 直观为什么重要？

能凭直觉说明结论为什么正确的论证实际上更值得信赖，而不是在未作理解的情况下展示所谓“数学严格性”的论证。 - E. T. Jaynes

任何知识点都有证明，但教学不是教证明+教代码，对定理的直观理解非常重要。

了解定理的直观解释还有助于培养数学直觉。

直观

• 如何形成对定理的直观理解？

应该相信，中学和本科阶段 的数学知识都有直观的理解方法。在此基础上，证明是很自然的，只是直观的自然语言翻译成严谨的数学语言的过程。

然而，网上阐述证明的资料很多，给出直观解释的资料却很少。在备课时，我会去 CF catelog 找灵感，或者和其他人（网友/老师/学生）讨论。

举例子

理解具体的例子往往比理解抽象的概念容易得多。很多学生看完概念后似懂非懂，看完例子后才“恍然大悟”。合适的例子还能帮助学生加深印象或发现特殊情况。

然而，一些学生过分依赖具体的例子来理解知识。经常有学生说“还是不太懂，能再举个例子吗”。学生最后声称自己懂了，但可能只是大量例子拟合出来的条件反射。问题在于抽象能力不足 + 不习惯数学语言，这对数学板块来说是致命的。

应该鼓励学生自己构造例子。

证明

• 应该怎么讲证明？

算法竞赛不是数学竞赛，证明的完整性和严谨性都不是第一位的！

尽力提供“自然”的证明，让学生把握证明的整体思路，了解每一步的动机。

哪些证明应该深入讲解？

• 思路很关键，不讲就没法掌握定理
• 方法很经典，能应用到很多题目中

在这些情况下，可以考虑少讲或不讲证明：

• 过程非常平凡，学生能自行完成
• 方法太特殊，没有可扩展性

如果未给出详细证明，可以提供资料（讲义、博客等）供感兴趣的学生课后查阅。

代码讲解

与其他模块相比，数学模块的代码讲解没有什么特别之处。

第二部分：具体问题

PPT：质数与因数、筛法

质数与因数

唯一分解定理：思考数论问题的重要突破口

筛法

朴素筛：调和级数复杂度

欧拉筛：怎么保证每个数只被它的最小质因子筛一次

讲义：最大公约数

裴蜀定理

可以用这样一个场景引入：

一个商店只接受面额为 和 的两种货币，可以找零。你能不能购买价格为 的商品？价格为 的商品呢？价格为 的商品呢？

扩展欧几里得算法

• 有两种讲法：
  • 讲法一与数学课本类似，取两个数为例进行辗转相除法，即每次用上一次的除数除以上一次的余数，直到余数为 为止。最后代入还原得到一组解。（讲法一示例）
  • 讲法二是纯数学推导，抽象、简洁、与代码的形式一致，推荐这种讲法。
• 所有的解（通解）
• 解线性同余方程
• 经典题目：洛谷 P1516 青蛙的约会

讲义：快速幂、费马小定理、乘法逆元

快速幂

举例子：

费马小定理

费马小定理的证明比较独特，几乎没有可扩展性。但有一点比较重要，应该作为常识记忆：

若 是质数且 ，则 是 的一个排列。

乘法逆元

逆元素是指可以取消另一给定元素运算的元素。初学者往往难以理解逆元，可以类比倒数。

一定要搞清楚几个问题：

• 逆元存在的条件
• 模数为质数时怎么求逆元，模数为合数时怎么求逆元
• 快速预处理多个数的逆元

有些逆元不存在的题需要用到 “扩大模数，保留因子” 的技巧，先不讲，学生遇到再说。

威尔逊定理

讲法：逆元成对存在。

很简单的小定理，有印象即可。题目很少见，也可以出得很难，如 CF1957 E. Carousel of Combinations。