【数论/学习笔记】Dirchlet 卷积，Mobius 反演及其应用

· · 个人记录

Dirchlet 卷积

算术函数

一个 \mathbb{N} \to \mathbb{C} 的函数 f 称作算术函数。

若 \forall \gcd{(a,b)}=1 ，有 f(ab)=f(a)f(b)，则称 f 为积性函数。

若 \forall a, b \in \mathbb{Z} ，有 f(ab)=f(a)f(b)，则称 f 为完全积性函数。

容易看出，完全积性函数所构成的集合是积性函数构成的集合的真子集。

例如，Euler 函数 \varphi{(x)} 就是一个积性函数（不是完全积性函数！）。

定义 Mobius 函数

\mu{(x)}=\begin{cases} 1, \text{若 x 为 1} \\ 0, \text{若 x 含平方素数因子} \\ (-1)^r, \text{若 x 可以表示为 r 个互异的素数之积} \end{cases}

Mobius 函数是完全积性函数。

积性函数一般都可以在线性筛的时候顺便筛出。

如筛 Mobius 函数：

int n=MAXN;
mob[1]=1;
for (int i=2; i<=n; ++i) {
    if (!v[i]) {
        prime[++tot]=i; mob[i]=-1; v[i]=1;
    }
    for (int j=1; j<=tot; ++j) {
        if (i*prime[j]>n || prime[j]>i) break;
        v[i*prime[j]]=1;
        if (i%prime[j]==0) mob[i*prime[j]]=0;
        else mob[i*prime[j]]=-mob[i];
    }
}

Dirchlet 卷积

对于两个算术函数 f(x), g(x)，定义其 Dirchlet 卷积：

(f\ast g)(n)=\sum_{d \mid n} f(n)g(\frac{n}{d})

其中 \sum_{d \mid n} 表示对所有 n 的正约数 d 求和。

也可以这么写：

(f\ast g)(n)=\sum_{d_1d_2=n} f(d_1)g(d_2)

我们有如下性质：

（1）交换律：

f\ast g=g\ast f

待填坑

例题

[SDOI2015] 约数个数和

Statement

给定 n, m，求

\sum_{i=1}^{n}\sum_{j=1}^{m} d(i\cdot j)

其中 d(x) 表示 x 的正约数个数。

Solution

我们知道，若 x\mid i, y\mid j，则xy \mid ij。

于是对于 d(x) 我们有

\boxed{d(ij)=\sum_{x\mid i}\sum_{y \mid j}[\gcd(x,y)=1]}

其中 [x=i] 即

1, \text{if x equals to i} \\ 0, \text{if x doesn't equal to i} \end{cases}

刚开始看到这个式子的时候我是很疑惑的，难道 \gcd(x,y) \neq 1 时 xy 就不是 ij 的因数了嘛。

诶，为了理解这个，我们可以手玩一下。比如当 i=2, j=4 的时候，我们可以在不加限制条件的情况下，枚举一下 x, y 的取值。

x=1: y=1, 2, 4 x=2: y=1, 2, 4

我们发现，这样一来 2\times 4 即 8 就有 6 个因数了。但实际上 8 的正因数只有 4 个（1, 2, 4, 8）。

诶，仔细观察下，我们发现，它枚举重复了。

然而对于因数为 $8$ 的情况，我们注意到，实际上 $8=4\times 2=2\times(2\times1)$，已经被 $x=2, y=1$ 的情况生成了。 于是我们加上限制条件枚举下。 $$x=1: y=1, 2, 4$$ $$x=2: y=1$$ 我们发现，这样子确实不重不漏地计出了 $ij$ 的因数个数。 --- 下一步，我们不妨把它应用回原式上，得到 $$\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x\mid i}\sum_{y \mid j}[\gcd(x,y)=1]$$ ~~四个 Sigma 看着就恐怖。~~ 我们可以将因数 $x, y$ 提到前面来计算。 因为 $1\sim n$ 里必然有 $\lfloor\frac{n}{x}\rfloor$ 个 $x$ 的因数，对于 $y$ 同理，我们可以得到 $$\sum_{x=1}^n\sum_{y=1}^m\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor[\gcd(x,y)=1]$$ 令 $x=i$，$y=j$，得到 $$\sum_{i=1}^n\sum_{j=1}^m\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor[\gcd(i,j)=1]$$ --- 于是考虑开始反演。 我们有 Mobius 反演的公式 （1） $$f(x)=\sum_{\textcolor{red}{d \mid x}} g(d) \iff g(x)=\sum_{\textcolor{red}{d \mid x}} \mu{(\textcolor{blue}{d})}f(\textcolor{blue}{\frac{x}{d}})$$ （2） $$f(x)=\sum_{\textcolor{red}{x \mid d}} g(d) \iff g(x)=\sum_{\textcolor{red}{x \mid d}} \mu{(\textcolor{blue}{\frac{d}{x}})}f(\textcolor{blue}{d})$$ 于是我们设 $$\boxed{f(x)=\sum_{i=1}^n\sum_{j=1}^m\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor[\gcd(i,j)=\textcolor{red}{x}]}$$ 设 $$\boxed{g(x)=\sum_{x \mid d} f(d)}$$ 则 $$g(x)=\sum_{i=1}^n\sum_{j=1}^m\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor[\textcolor{red}{x\mid \gcd(i,j)}]$$ 为什么是这么变形的呢？首先我们知道，$d$ 一定为 $x$ 的倍数。那么只要 $x\mid \gcd{(i,j)}$，我们就一定有 $\gcd(i,j)=d$。 我们把 $x$ 提出来，显然 $1\sim n$ 中只有 $\lfloor\frac{n}{x}\rfloor$ 个数是 $x$ 的因数，于是我们有 $$\boxed{g(x)=\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{x}\rfloor}\lfloor\frac{n}{i\textcolor{red}{x}}\rfloor\lfloor\frac{m}{j\textcolor{red}{x}}\rfloor}$$ 由 Mobius 反演的公式 2 可以得到 $$f(x)=\sum_{x\mid d} \mu(\frac{d}{x})g(d)$$ 注意到所求即为 $f(1)$，代入得 $$f(1)=\sum_{1\mid d}\mu(d)g(d)$$ 即 $$f(1)=\sum_{i=1}^{\min(n,m)}\mu(i)g(i)$$ 故 $$\text{ans}=\left(\sum_{i=1}^{\min(n,m)}\mu(i)\right)\left(\sum_{i=1}^{\min(n,m)}g(i)\right)$$ --- 我们可以预处理出 $\mu(i)$ 的前缀和，这部分是 $\Theta(1)$ 的。那么右边那部分呢？ $$\begin{aligned}\sum_{i=1}^{\min(n,m)}g(i)=\sum_{k=1}^{\min(n,m)}\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{x}\rfloor}\lfloor\frac{n}{ik}\rfloor\lfloor\frac{m}{jk}\rfloor \end{aligned}$$ 我们可以用**数论分块** $\Theta(\sqrt{k})$ 地预处理出 $$\sum_{i=1}^{k}\lfloor\frac{k}{i}\rfloor$$ 那么，可以 $\Theta{(n\sqrt{n})}$ 地求出 $$\sum_{k=1}^n\left(\sum_{i=1}^{k}\lfloor\frac{k}{i}\rfloor\right)$$ $n$ 的范围是 $5\times10^4$ 的，此时 $n\sqrt{n} \lt 2\times 10^8$。可以通过。 那么我们不妨记 $$h(x,y)=\sum_{i=1}^{x}\lfloor\frac{y}{i}\rfloor$$ $$\begin{aligned}\sum_{i=1}^{\min(n,m)}g(i)=\sum_{k=1}^{\min(n,m)}\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{x}\rfloor}\lfloor\frac{n}{ik}\rfloor\lfloor\frac{m}{jk}\rfloor \\ =\sum_{k=1}^{\min(n,m)}\lfloor\frac{h(n,\lfloor\frac{n}{x}\rfloor)}{k}\rfloor\lfloor\frac{h(m,\lfloor\frac{m}{x}\rfloor)}{k}\rfloor \end{aligned}$$ 这又是一个**数论分块**的形式。于是每个询问可以在 $\Theta(\sqrt{n})$ 内完成。 总时间复杂度：$\Theta(\left(T+n\right)\sqrt{n})$。最高不超过 $4 \times 10^8$，如果常数小一些，可以通过此题。