前置知识

积性函数

若函数 为正整数 对任意的满足 的两个数有

，则称 为积性函数。

特别的，若对任意 ，则称 为完全积性函数。

常见积性函数

莫比乌斯函数

约数函数

对于迪利克雷卷积的乘法单位函数 （完全积性）

迪利克雷卷积

定义

对于两个以正整数为定义域的函数 ,它们的迪利克雷卷积为：

性质

满***换律，结合律，分配律，并有单位元；

若 均为积性函数，那么它们的迪利克雷卷积也为积性函数。

莫比乌斯反演

两种形式

第一种：约数形式

第二种：倍数形式

注：利用上述性质可以证明。其本质是容斥原理，可以看学长大大的博客 HDU-6363 bookshelf 莫比乌斯反演 理解一下

注：都必须是积性函数。

整除分块

用于求解类似于 的问题。

我们发现， 的取值非常有限，最多只有 种。

证明： 时，最多 种；

时，， 最多 种。

然后我们就求一下 的 。

初始令 ，找到对应的 ，最后令 。

关于 的求法见 整除分块

注：两个变量的时候同理，令 。