数论与积性函数：线性筛法、欧拉函数与莫比乌斯反演

"这篇资料主要涉及的是ACM算法竞赛中的数论方向，特别是线性筛法和积性函数的相关知识，出自南京外国语学校贾志鹏的分享。" 在这份资料中，首先介绍了两种常见的质因数筛选方法：Eratosthenes筛法（埃拉托斯特尼筛法）和Euler筛法（欧拉筛法）。Eratosthenes筛法的时间复杂度为O(𝑁loglog𝑁)，空间复杂度为O(𝑁)；而Euler筛法则通过只标记每个合数最小的质因数，达到时间复杂度为O(𝑁)的效果。这两种方法在算法竞赛中常用于快速找出一定范围内的所有质数。 接下来，资料讲解了积性函数的概念。积性函数是指在正整数集上的函数，满足对于互质的两个正整数𝑎和𝑏，其函数值乘积等于分别对𝑎和𝑏求函数值的乘积。完全积性函数进一步要求对于所有正整数𝑎和𝑏，不论是否互质，该性质依然成立。积性函数的一个重要性质是它们在1上的值总是1。 其中提到了两个重要的积性函数：欧拉函数𝜑(𝑛)和莫比乌斯函数𝜇(𝑛)。欧拉函数表示1到𝑛中与𝑛互质的整数个数，它不是完全积性函数，但对于质数𝑝的幂Pk，欧拉函数有特别的计算公式：𝜑(𝑝𝑘) = 𝑝𝑘 - 𝑝𝑘-1 = 𝑝-1𝑝𝑘-1。欧拉定理是欧拉函数的一个重要应用，它指出如果𝑎和𝑛互质，则𝑎𝜑(𝑛) ≡ 1 (mod 𝑛)，特殊情况即费尔马小定理，这对于计算模运算中的乘法逆元非常有用。 莫比乌斯函数则是另一个关键的积性函数，其值为1、-1或0，分别对应于其参数为1、非1的平方自由数和非平方自由数。莫比乌斯反演是一个强大的工具，它建立了两个积性函数之间的关系，通常用于简化数论问题的解决。 资料中还提到，莫比乌斯反演与容斥原理有着紧密联系。通过莫比乌斯反演，我们可以将某些问题转换为求积性函数的和，这对于处理与约数相关的计数问题非常有效。例如，函数𝑓𝑛=∑(𝜑(𝑑)/𝑛)，其中𝑑|𝑛，可以通过莫比乌斯反演来求解。 这份资料涵盖了数论在ACM算法竞赛中的基础和高级应用，包括质因数筛选和积性函数的理论与实践，是学习和准备算法竞赛的宝贵资源。