Part 1 需要重写
GitPinkRabbit opened this issue · 0 comments
GitPinkRabbit commented
目前的问题有:
- 应当在每一节开头写一到两页导言的,以达到引入本节内容的目的。整个课件的开头也同样地需要导言?
- 整除结构的篇幅不够大,这里在初学时就能引入的东西很多,例如:
- 因数个数 / 因数和的标准分解形式的式子(乘法分配律)
- 满足 x | n 的 x 之间的结构(一角在原点的超长方体)
- 满足 d | x | n 的 x 之间的结构(两对角固定的超长方体)
- 图太少了?特别是关于上一条的图
- 在素因数分解的时候,另一个考虑是预处理出来值域根号范围内的所有素数,然后试除,这样每次询问最坏复杂度少个 log
- 由此需要大概介绍一下素数分布的 O(n / log n),这部分应当开一个专门的部分来讲
- 在标准分解中,如果只要求指数的结构,而底数不重要(例如求因数个数的时候),常见的 trick
- 说明白点,也就是只需要枚举到三次根号的地方,然后(不对啊这个地方一般情况的话需要一个 Miller–Rabin,特殊情况有 AGC003D,我们需要更多例子,然后选一个最合适的)
- 当然,具体的算法相关的内容要放在讲完试除法后
- 小学数学教材那个图要更新(它有必要存在吗?),由于没有找到不歪的电子影印版,我淘宝买的教材已经在路上了
- Diophantus 方程这东西其实有点蠢,因为算法竞赛中确实并不单独提它。魔怔的水果方程太刻意了(这玩意儿 CP 里也不用会算,没有拓展性,处境同样尴尬的还有 Pell 方程,有关于它的比较好的题吗?)
- #10
- #11
- 需要先引入在计数题里的最简单应用,也就是 “答案可能很大,请你对 m 取模后输出” 的那套题目。也就是加法和乘法混合的运算最后要取模的话可以每一步分别取模,其中也包括对快速幂的引入。这部分不用与剩余类/剩余系结构捆绑的原因是要先让读者熟悉一下理念,在我们强调模数 m 不能变的情况下,然后接受剩余类的概念就会容易一些
- 由于前面的一系列问题,在加大篇幅后,预计要把整个解线性 Diophantus 方程那一节砍了,也就是先不提 Bézout 定理了。这个部分要放到 Part 2 里,Part 2 里介绍到欧拉定理为止应该就够了