狄利克雷相关 更新于 2026/7/5 10:46:12 作者

command_block

狄利克雷前缀和

首先需要掌握 位运算卷积(FWT)与其扩展 ,否则可能无法理解某些内容。

设 $A^+=A*I$ ,即倍数求和, $A^-=A*\mu$ ,则倍数差分(逆运算)。

倍数求和直接枚举倍数暴力算即可,复杂度$O(n\log n)$.

倍数差分可以莫比乌斯反演:

设容斥系数为$g$,有$A^-[n]=\sum\limits_{i=1}g(i)A[i]=\sum\limits_{i=1}g(i)\sum\limits_{i|j}A^-[j]$

提取$A^-[j]$的贡献系数 : $\sum\limits_{i|j}g(i)=[j=n]$,即能推出$g(i)=[n|i]\mu(i/n)$

回代可得$A^-[n]=\sum\limits_{n|i}\mu(i/n)A[i]$,这同样可以枚举倍数达到$O(n\log n)$.

我们在计算 and 卷积的时候,可以暴力枚举补集,但是复杂度为$O(3^n)$不优。

类似地,我们在这里暴力枚举倍数也不够优。

• P5495 Dirichlet 前缀和

这是前缀和而不是本文的倍数求和,不过原理类似。

考虑每个质因数是一维,做高维前缀和(其实就是卷 $I$ ),代码是这样的:

for(int i=1;i<=tn;i++)
    for(int j=1;j*p[i]<=n;j++)
      F[j*p[i]]+=F[j];

类似地,有约数前缀差分(其实就是卷 $\mu$ )

for(int i=1;i<=tn;i++)
    for(int j=n/p[i];j;j--)
      F[j*p[i]]-=F[j];

以后想卷 $I,\mu$ 的时候,这样写会比暴力狄利克雷卷积快得多,还不用筛。

约数后缀和:

for(int i=1;i<=tn;i++)
    for(int j=n/p[i];j;j--)
      F[j]+=F[j*p[i]];

约数后缀差分:

for(int i=1;i<=tn;i++)
    for(int j=1;j*p[i]<=n;j++)
      F[j]-=F[j*p[i]];

根据埃氏筛法的复杂度分析,上述代码的复杂度均为 $O(\sum_{p}^n\frac{n}{p})=O(n\log\log n)$

• 例题 : P2714 四元组统计

• 求 $\gcd$ 卷积

形如 $C[n]=\sum\limits_{(i,j)=n}A[i]B[j]$ 的卷积,被称为 $\gcd$ 卷积。

我们可以先计算 $C^+[n]=\sum\limits_{n|(i,j)}A[i]B[j]$ ,然后再差分即可得到 $C$ .

$C^+[n]=\sum\limits_{n|(i,j)}A[i]B[j]$

$=\sum\limits_{n|i,n|j}A[i]B[j]$

$=\big(\sum\limits_{n|i}A[i]\big)\big(\sum\limits_{n|j}B[j]\big)$

$=A^+[i]B^+[j]$

• 这从向量变换的角度容易理解:

  $\gcd$ 的本质就是对每个质因子维度取 $\min$.

  类比 and 卷积,先要做高维后缀和,点乘再差分即可得到答案。

  对应到 $\gcd$ 卷积上,即先要倍数求和,点乘再倍数差分。

• 快速狄利克雷卷积

可用于加速某些题目的预处理。

我们按照枚举倍数的传统方法计算狄利克雷卷积,复杂度是 $O(n\log n)$ 的。

前面讲到过,对于卷 $I,\mu$ 的特殊情况,可以理解成在高维空间的前缀和/差分,从而使用高维变换优化。

实际上,对于任意的积性函数,也有类似的方法。

设 $F$ 为积性函数, $G$ 不是,欲求 $F*G$ 的前 $n$ 项。

我们把 $F$ 分解为若干个只和某个素数 $p$ 有关的函数(变换) 的卷积,即 :

$F_p(n)=\begin{cases}F(n)&(n=p^k)\\0&{\rm otherwise}\end{cases}$

然后则有 $F=\prod\limits_{p\in {\rm Prime}}F_p(n)$ ,这里的乘法是狄利克雷卷积。

简略证明 : 容易发现 $F_{p_1}*F_{p_2}$ 能够得到 $n=p_1^{k_1}p_2^{k_2}$ 处的所有值,可以进一步推广到不交的质数集合卷积的情况。

也即 : 可以把一个积性函数拆成 $\pi(n)$ 个只与单个质数有关的积性函数卷积。

我们把这些函数分别卷到 $G$ 上去,就能得到答案。

考虑 $(G*F_p)(n)=\sum\limits_{d|n}G(n/d)F_p(d)$

$=\sum\limits_{p^k|n}G(n/p^k)F_p(p^k)$

考虑枚举每个 $p^k$ 的倍数计算该和式。(可以预先保存需要的 $G$)

考虑单个质数 $p$ ,其贡献的复杂度为 $O\Big(\sum\limits_{k=1}^{∞}n/p^k\Big)$

使用等比数列可算得其为 $O(\frac{n}{p-1})$ 其实也与 $O(\frac{n}{p})$ 同级。

所以复杂度仍然是 $O(\sum_{p}^n\frac{n}{p})=O(n\log\log n)$。

此外,对于每个 $p^k$ 都需要求出 $F$ ,这样的 $p^k$ 的个数是 $O(n/\log n)$ 的。

对于 $p\leq \sqrt{n}$ 的部分,贡献不超过 $O(\pi(\sqrt{n}\log n))=O(\sqrt{n})$ ,可不计。

对于 $p>\sqrt{n}$ 的部分,指数只能是 $1$ 贡献不超过 $O(\pi(n))=O(n/\log n)$。

所以,我们只需要为求解单个 $F(p^k)$ 找到一个 $O(\log n)$ 以内的复杂度即可。

• 例题 : P6222 「P6156 简单题」加强版

狄利克雷生成函数

对于一个数论函数， $F$ ,定义其狄利克雷生成函数为 ：

$$F(s)=\sum\limits_{i=1}\dfrac{F[i]}{i^s}$$

由于 $a^s*b^s$ 会贡献到 $(ab)^s$ ，两个数论函数的狄利克雷卷积就对应其 $\rm DGF$ 的卷积。

你可能会问为啥不用 $i^s$ 而用 $\dfrac{1}{i^s}$ ? 前者会导致级数不收敛……

本文中讨论的数论函数都是积性函数。

• 常见积性函数的 $\rm DGF$

似乎没有贝尔级数好用，先咕了。

• 狄利克雷除法

和生成函数没啥关系，只是数论函数求逆罢了。

$F*G=e$

$G[1]=1,\quad\sum\limits_{d|n}F[n/d]G[d]=0$

$F[1]G[n]+\sum\limits_{d|n,d≠n}F[n/d]G[d]=0$

$G[n]=-\sum\limits_{d|n,d≠n}F[n/d]G[d]$

复杂度 $O(n\log n)$。

当然还有更快的办法，先按照上文的方法将积性函数划分成若干个单素数积性函数，分别（多项式）求逆后，再卷积。

这样能做到 $O(n\log\log n)$。

• 狄利克雷 $\ln$

回忆 $\ln A=B\Rightarrow B=∫\dfrac{A'}{A}$ ,我们只需要再定义出导数和积分。

回忆指数函数的求导法则 $(a^x)'=a^x\ln a$

但是此处 $\ln a$ 无定义，一种广为流传的做法是，定义 $\ln n$ 为 $n$ 的质因子幂次总和。

这样就能满足 $\ln ab=\ln a+\ln b$ 的关键性质。

积分只需要定义为逆运算即可。

• 狄利克雷 $\exp$

要求 $A[1]=0$

回忆 $\exp A=B\Rightarrow \ln B=A\Rightarrow A'=\dfrac{B'}{B}\Rightarrow A'B=B'$

$\Rightarrow \sum\limits_{d|n}B[d]A'[n/d]=B'[n]$

$A[1]B[n]+\sum\limits_{d|n,d≠n}B[d]A'[n/d]=B'[n]$

$B'[n]=\sum\limits_{d|n,d≠n}B[d]A'[n/d]$

这就能 $O(n\log n)$ 递推了。