浅谈积性函数的求和
本文最后更新于：2022年12月26日 下午
Part 0 前置
0. 声明与约定
- ，表示 在区间 内的和。特殊地，当 时，。
- ，表示 在区间 内的和。此外，始终有 。
1. 艾佛森括号
艾佛森括号 ，即如果表达式成立就为 ，否则为 。
2. 数论函数
指定义域为正整数，陪域为复数的函数，主要包括积性函数和加性函数。
如不加以说明，以下所有“函数”均指数论函数，“数”均指整数或正整数。
3. 函数运算
加法
。
加法满足以下性质：
- 交换律：。
- 结合律：。
乘法
。
乘法满足以下性质：
- 交换律：。
- 结合律：。
- 分配律：。
- 单位元：。
狄利克雷卷积
。
狄利克雷卷积满足以下性质：
- 交换律：。
- 结合律：。
- 分配律：。
- 单位元：。
- 逆元：如果 ，则称 为 的狄利克雷逆元，记作 。且 。
4. 加性函数
满足 且 的函数 称为加性函数。特别地，当 不互质时 仍然成立的函数 称为完全加性函数。
加性函数一般需要唯一分解定理。设 ，则常见的加性函数有：
- ，表示 的所有质因子数目。（完全加性）
- ，表示 的不同质因子数目。
- ，表示 的所有质因子和。（完全加性）
- ，表示 的不同质因子和。
5. 积性函数
满足 且 的函数 称为积性函数。特别地，当 不互质时 仍然成立的函数 称为完全积性函数。
常见的积性函数有：
- 单位元函数 。（完全积性）
- 幂函数 。其中 简记作 或 ， 简记作 。（完全积性）
- 约数函数 。其中 简记作 或 ， 简记作 。
- 欧拉函数 ，表示 内与 互质的数的个数。
- 莫比乌斯函数 。换句话说，设 ，则
积性函数有以下性质：
- 如果两个函数是积性函数，那么它们的乘积也是积性函数。
- 如果两个函数是积性函数，那么它们的狄利克雷卷积也是积性函数。
- 如果两个函数是完全积性函数，那么它们的狄利克雷卷积不一定是完全积性函数（示例：， 和 均为完全积性函数，但 不是完全积性函数）。
6. 狄利克雷卷积结论
- （莫比乌斯变换/反演）
- （欧拉变换/反演）
- （上两个结论的结合）
7. 伪代码约定
- 大写衬线粗体 () 表示基本词汇（关键字）。
- 小写斜体 () 表示变量。
- 小写衬线字体 () 表示数组等支持随机访问下标的数据结构。
- 大写衬线字体 () 表示用自然语言描述的过程。
- 小写等宽字体 () 表示数组、链表等支持在尾部插入和遍历的数据结构。
- 小写无衬线字体 () 表示输入数据。
Part 1 基本函数 (Easy)
实现难度：Past 1
时间复杂度：
空间复杂度：
Part 2 简单前缀和 (Normal)
1. 暴力筛
实现难度：Past 2
要求：
- 能通过其所有约数快速转移（示例： ）。
时间复杂度：
空间复杂度：
优点：
- 推导简单。
缺点：
- 速度过慢（大约只能过 级别）。
- 适用范围小。
2. 埃氏筛
实现难度：Past 3
要求：
- 能通过其所有质因子快速转移（示例：若 ，则 ）。
时间复杂度：
空间复杂度：
优点：
- 推导简单。
缺点：
- 速度较慢（大约只能过 级别）。
算法流程
3. 线性筛
实现难度：Present 6
要求：
- 是积性函数或加性函数。
- 在质数处能够在低于 的时间里求值。
- 能够从在一个数处的值快速得到在它与一个质数的乘积处的值。
时间复杂度：
空间复杂度：
优点：
- 速度较快（大约能过 级别）。
缺点：
- 推导较麻烦。
- 仅适用于积性函数和加性函数。
- 不适用于 很大的情况。
算法流程
算法流程如下：
设置 为质数时的 。
设置 为质数 的倍数时的 。
筛法推导
思考以下两个问题：
- 在质数 处的值为多少？
- 在质数的整数次幂 处的值为多少？
这两个问题恰好对应上面标红的两处。
设第二个问题的答案为 。
设 ，则显然 。那么 ，即 处的值为 。
实例
莫比乌斯函数
根据定义就可以直接得出结论。首先，我们知道 。
当 为质数 的倍数时，显然 含有 这个因子，所以 。
当 与质数 互质时，如果 含有平方因子，那么 也含有平方因子，因此 。
如果 不含有平方因子，那么 也不含有平方因子，且显然有 。因此 。
综上，当 与质数 互质时，。
但是我们还是考虑用正常流程推导一遍：
1. 在质数 处的值为多少？
根据定义，显然为 。
2. 在质数的整数次幂 处的值为多少？
根据定义，显然有 ，那么 ，所以 。
欧拉函数
1. 在质数 处的值为多少？
显然，当 为质数时， 内的每个数都与 互质，所以值为 。
2. 在质数的整数次幂 处的值为多少？
显然，对于质数 ，含有 因子的数与 不互质， 内含有 因子的数共有 个，所以 。那么显然 ，因此 。
（待补充……）