积性函数
定义
函数 满足 且 都有 ，则 为积性函数。
函数 满足 且 都有 ，则 为完全积性函数。
例子
- 单位函数：。（完全积性）
- 恒等函数：。（完全积性）
- 常数函数：。（完全积性）
- 除数函数：。 通常简记作 或 ， 通常简记作 。
- 欧拉函数：。
- 莫比乌斯函数：，其中 表示 的本质不同质因子个数，它是一个加性函数。
狄利克雷卷积
对于两个数论函数 和 ，则它们的狄利克雷卷积得到的结果 定义为：
可以简记为：。
性质
交换律：。
结合律：。
分配律：。
等式的性质： 的充要条件是 ，其中数论函数 要满足 。
例子
- )
莫比乌斯反演
莫比乌斯函数性质
- ，即 ，
莫比乌斯变换/反演
，那么有 。
用狄利克雷卷积表示则为 ，有 。
称为莫比乌斯反演， 称为莫比乌斯反演。
杜教筛
杜教筛被用于处理一类数论函数的前缀和问题。对于数论函数 ，杜教筛可以在低于线性时间的复杂度内计算 。
可以构造恰当的数论函数 使得：
- 可以快速计算 。
- 可以快速计算 的单点值，用数论分块求解 。