狄利克雷卷积与杜教筛

狄利克雷卷积

积性函数

定义：

对于数论函数$f$，若对于任意互质的数$x,y$，满足$f(xy)=f(x)f(y)$，则$f$为一个积性函数。

事实上，我们见过的大部分数论函数都是积性函数，常见的如：

$\mu(x)$，莫比乌斯函数，在莫比乌斯反演有讨论过。
$\varphi(x)$，欧拉函数。
$d(x)$，表示$x$的约数个数。
$\sigma(x)$，约数和函数。
$\epsilon(x)$，狄利克雷卷积的原函数，即$\epsilon(x)=[x=0]$。
$id(x)$，定义$id(x)=x$。
$I(x)$，定义$I(x)$函数值恒为$1$，即$I(x)=1$。

这只是一小部分，其中有些函数的性质待会会分析。

狄利克雷卷积

定义：

对于数论函数$f$和$g$，定义它们的狄利克雷卷积为：

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

其中$(f*g)$表示$f$和$g$的狄利克雷卷积。

然后有一个很重要的性质，对于积性函数$f$和$g$，它们的狄利克雷卷积也是个积性函数。

证明很简单，设质数$p$和$n$互质，则：

$(f*g)(np)=\sum_{d|np}f(d)g(\frac{np}{d})$

然后展开：

$(f*g)(np)=\sum_{d|n}f(d)g(\frac{np}{d})+\sum_{d|n}f(pd)g(\frac{n}{d})$

由于$f,g$为积性函数，可以拆开提出来：

$(f*g)(np)=(g(p)+f(p))\sum_{d|n}f(d)g(\frac{n}{d})$

注意到第一项就是$(fg)(1)$，第二项为$(fg)(n)$，所以：

$(f*g)(np)=(f*g)(n)*(f*g)(p)$

命题得证。

根据这个，可以有效的判断函数是否为积性函数。

狄利克雷卷积具有的一些性质：

交换律：$fg=gf$。
结合律：$f(gh)=(fg)h$。

证明很显然，这里就不赘述了。

然后考虑一些常见函数的狄利克雷卷积：

1．$\epsilon(x)$。

对于任意数论函数$f$，根据定义，拿一个卷上一个$\epsilon$，得到：

$(f*\epsilon)(n)=\sum_{d|n}f(d)\epsilon(\frac{n}{d})=f(n)$

即$f*\epsilon=f$，

然后我们可以惊奇的发现，卷完了之后得到了他本身，所以说这个函数就是狄利克雷卷积的单位元。

2．$\mu(x)$。

首先我们知道这样一个式子：

$\sum_{d|n}\mu(d)=[n=1]$

写成狄利克雷卷积形式就是：

$\mu*I=\epsilon$

３．$\varphi(x)$。

这个函数有一些很妙的性质，比如说(~~众所周知~~)：

$\sum_{d|n}\varphi(x)=n$

证明如下：

设$f(n)=\sum_{d|n}\varphi(d)$，由上面提到的狄利克雷卷积性质可得，$f$为积性函数。

对于$n$的每一个质因数进行考虑，即：

$f(x^{p})=\sum_{d|x^p}\varphi(d)=\sum_{i=0}^p\varphi(x^i)$

因为$\varphi(x^p)=\varphi(x^{p-1})*p$，$\varphi(x)=x-1$可得：

$f(x^p)＝x-1+\sum_{i=1}^p(x-1)*x^{i}$

由等比数列求和可得$f(x^p)=x^p$，又由$f$为积性函数可得$f(n)=n$，得证。

写成狄利克雷卷积的形式就是：

$\varphi*I=id$

然后注意到$\mu*I=\epsilon$，于是尝试在等式两边分别卷上一个$\mu$：

$\begin{align} \varphi*(I*\mu)&=id*\mu\\ \varphi*\epsilon&=id*\mu\\ \mu*id&=\varphi \end{align}$

写成一般形式就是：

$\sum_{d|n}\mu(d)*\frac{n}{d}=\varphi(n)$

这个式子也很常用的。

杜教筛

~~前置知识终于讲完了~~

对于积性函数$f$，现在考虑求$\sum_{i=1}^nf(i)$。

当然我知道你会线筛，但是有一些小清新(无良)出题人把数据开到$1e9$级别，你就做不了了，所以需要更快的算法。

设$S(n)=\sum_{i=1}^{n}f(i)$。

考虑先拿一个函数和$f$做卷积，先不考虑这个函数是啥，先设它为$g$，则：

$(f*g)(n)=\sum_{d|n}^{n}f(d)g(\frac{n}{d})$

对这个函数前缀和一下：

$\sum_{i=1}^n\sum_{d|i}g(d)f(\frac{n}{d})=\sum_{d=1}^{n}g(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)=\sum_{d=1}^{n}g(d)S(\lfloor\frac{n}{d}\rfloor)$

中间交换求和符号就不赘述了。

然后有一个很显然的式子：

$g(1)S(n)=\sum_{d=1}^{n}g(d)S(\lfloor\frac{n}{d}\rfloor)-\sum_{d=2}^{n}g(d)S(\lfloor\frac{n}{d}\rfloor)$

然后把等号右边第一项换一下：

$S(n)=\sum_{i=1}^{n}(f*g)(i)-\sum_{d=2}^{n}g(d)S(\lfloor\frac{n}{d}\rfloor)$

剩下的事情就很显然了，如果我们能凑出一个$g$，使得它和$f$的卷积的前缀和很好算，它也很好算，我们就可以先预处理出前$1e7$左右的数据，然后记忆化递归处理$S$。

至于$g$，因题目不同而不同，做多了也就有经验了。

注意上试是杜教筛的套路试子，如果不会推也没关系，记下来就好了。

这里还是举几个栗子吧：

１．$\sum_{i=1}^{n}\mu(i)$.

首先我们知道一个这样的东西：

$\mu*I=\epsilon$

对于$\epsilon$的前缀和，显然是$1$，

所以，令$g(n)=I(n)=1$，得到：

$S(n)=1-\sum_{i=2}^nS(\frac{n}{i})$

然后数论分块下就行了。

代码也很简单，记住一定要记忆化。

map<int,int > Mu;
int sum_mu(int n) {
	if(n<maxn) return mu[n];
	if(Mu[n]) return Mu[n];
	int T=2,res=1;
	while(T<=n) {
		int pre=T;T=n/(n/T);
		res=res-(T-pre+1)*sum_mu(n/T);T++;
	}
	return Mu[n]=res;
}