积性函数初步

数论分块

数论分块可以在 $O(\sqrt{N})$​ 的时间复杂度求出以下式子的值：

$$\sum_{i=1}^{n}\lfloor{\frac{n}{i}}\rfloor$$

通过打表发现，有许多 $\lfloor{\frac{n}{i}}\rfloor$​​ 的值是相同的且呈块状分布，设一段相同的值起始位置为 $l$​​ ，则其终止位置为

$$\lfloor{\frac{n}{\lfloor{\frac{n}{i}}\rfloor } }\rfloor$$

证明：

令 $p=\lfloor{\frac{n}{l}}\rfloor$​，则 $n=lp+c$​

若存在 $Δ \in N$​，使得 $\lfloor{\frac{n}{l+Δ}}\rfloor=p$​，则 $n=(l+Δ)p+c'$​

$\therefore lp+c=(l+Δ)p+c'$​

$$\begin{aligned} lp+c&=(l+Δ)p+c'\\ lp+c&=lp+Δp+c'\\ c&=Δp+c'\\ Δp&=c-c'\\ Δ&=\frac{c}{p}-\frac{c'}{p} \end{aligned}$$

显然，$Δ_{max}=\lfloor{\frac{c}{p}} \rfloor$

$$\begin{aligned} \therefore r&=l+\lfloor{\frac{c}{p}} \rfloor\\ &=\lfloor{\frac{pl}{p}}+\frac{c}{p}\rfloor\\ &=\lfloor{\frac{n-pl+pl}{p}}\rfloor\\ &= \lfloor{\frac{n}{\lfloor{\frac{n}{i}}\rfloor } }\rfloor \end{aligned}$$

所以每个块的区间为：$[l, \lfloor{\frac{n}{\lfloor{\frac{n}{i}}\rfloor } }\rfloor ]$​可以一直不断地跳区间即可

code

1
2
3
4

for(int l=1,r;l<=n;l=r+1){
	r=n/(n/l);
 	ans+=(r-l+1)*(n/l);
}

一些常见积性函数（务必记住一下函数的符号记法）

• 常数函数
• 单位函数: $\varepsilon$​ （下文提及）
• 恒等函数: $id(n)=n$
• 欧拉函数: $\varphi(n)=\sum_{i=1}^n [gcd(i,n)=1]$​ （不会证明其为积性函数的建议去重修欧拉函数）
• 除数函数1:$d(n)=\sum_{d|n}1$ （就是 $n$ 约数个数，根据定义证明即可）
• 除数函数$2$:$\sigma(n)=\sum_{d|n}d$ ）（$n$​ 约数和，根据定义证明即可）​
• 莫比乌斯函数 $w(n)$ 为 $n$ 本质不同质因子个数（就是有多少个不同的质因子）

狄利克雷卷积

对于两个数论函数 $f(x)$ 与 $g(x)$，定义其狄利克雷卷积的结果 $h(x)$ 为：

$$h(x)=\sum_{d|x}f(d)g(\frac{n}{d})$$

简记为：$h=f*g$

显然，狄利克雷卷积满足一下性质：

交换律 ：$f*g=g*f$

结合律：$(f*g)*h=f*(g*h)$

分配律 ： $(f+g)*h=f*h+g*h$

狄利克雷卷积运算的单位元：

$\varepsilon$​​ 函数是狄利克雷卷积运算的单位元，即对于任意的数论函数 $f$​，都有 $f*\varepsilon=f$

通过简单手算可知，$\varepsilon(n)=[n=1]$​

一些简单却非常重要的卷积例子：

我们将详细地给出下面四个例子的证明

1) 证：

$\sum_{d|n}\mu(d)$ 在 $n=1$ 时显然等于 $\varepsilon(1)$，我们来证明在 $n>1$ 时上式定为 $0$

由算术基本定理（唯一分解定理）可得：

$n=p_1^{k_1}\times p_2^{k_2}\times...\times p_m^{k_m}$​​

则有：

$$d=\prod_{i=1}^{m}p_i^{c_i}\ ,\ c_i\in[0,k_i]\ and \ c\in N$$

其实就因为 $d$ 是 $n$ 的因数，所以每一个 $d$ 定可以从 $n$ 的质因子中选出一坨相乘来表示

根据莫比乌斯函数的定义，如果 $d$ 选取的质数中出现一个质数的指数 $c_i$ 大于等于 $2$，则说明其有一个完全平方数因子，则 $\mu(d)$ 的值为 $0$,对 $\sum_{d|n}$ 的贡献为 $0$ 。

由此可知，对 $\sum_{d|n}$​ 有贡献的 $c_i$​​ 的值定为 $0$​ 或 $1$​ ，那么在 $m$​ 个质数中，每个质数的指数只有两种取值，总的来说共有 $2^m$​ 种取值。显然，$\sum_{i=1}^{m} c_i$​ 的值有一半为奇数，有一半为偶数，再结合莫比乌斯函数的定义来看，正负相抵，总的值也就为 $0$​

证毕。

2) 式过于简单，证明略

$3)$ 式过于简单，证明略

$4)$ 证：

欧拉函数性质： $n=\sum_{d|n} \varphi(d)$

令$f(n)=\sum_{d|n}\varphi(d)$，我们来证明 $f$​​ 为积性函数

$$n,m\in\N_+,gcd(n,m)=1\\ \begin{aligned} f(n)\times f(m)&=\sum_{d|n}\varphi(d)\times \sum_{d'|m}\varphi(d') \\ &=\sum_{d|n}\sum_{d'|m}\varphi(d)\times \varphi(d')\\ &=\sum_{d|n}\sum_{d'|m}\varphi(d\times d')\\ &=\sum_{d''|nm}\varphi(d'')=f(nm) \end{aligned}$$

说一下等式变化的第三步，由于 $n,m$ 的互质，所以 $d\times d'$ 其实上枚举了 $n\times m$​​ 的所有因数

综上可知，$f$ 为积性函数

由算数基本定理得：

$$n=p_1^{c_1}\times p_2^{c_2}\times ...\times p_k^{c_k}\\ \therefore f(n)=f(p_1^{c_1})\times f(p_2^{c_2})\times ...\times f(p_k^{c_k})\\ f(p^k)=\varphi(1)+ \varphi(p)+ \varphi(p^2)+..+\varphi(p^k)=1+(p-1)+(p^2-p)+...+(p^k-p^{k-1})=p^k\\ n=\prod_{i=1}^k f(p_i^{c_i})=\prod_{i=1}^{k}p_{i}^{c_i}=n\\ \therefore n=\sum_{d|n}\varphi(d)$$

$$n=\sum_{d|n}\varphi(d)\Longleftrightarrow \varphi*1=id\\ \begin{aligned} \therefore id*\mu&=\varphi*1*\mu\\ id*\mu&=\varphi*\varepsilon\\ id*\mu&=\varphi \end{aligned}$$

证毕。