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