狄利克雷生成函数浅谈
gxy001
2021-01-26 20:58:51
# 狄利克雷生成函数（$\text{DGF}$）浅谈
[更好的阅读体验](https://missingroom.github.io/_posts/2021-02-01-DGF%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/)
前置知识：无。
## 数论函数
定义域为正整数，陪域为复数的函数。
## 狄利克雷卷积
对于数论函数 $f,g$，定义它们的狄利克雷卷积为 $(f*g)(x)=\sum\limits_{d\mid x}f(d)g(\frac{x}{d})$。
换种容易理解的表示方式即 $(f*g)(x)=\sum\limits_{a\times b=x}f(a)g(b)$。
## 狄利克雷生成函数（$\text{DGF}$）
数论函数 $f$ 在 $i$ 处的点值表示为 $f_i$，则 $f$ 的狄利克雷生成函数 $F(x)=\sum\limits_{i=1}^\infin \frac{f_i}{i^x}$。
### 黎曼 $\zeta$ 函数
$\zeta(x)=\sum\limits_{i=1}^\infin \frac{1}{i^x}$，容易发现，这是常数函数 $I(x)=1$ 的 $\text{DGF}$。
这个函数与 $\text{OGF}$ 的 $\frac{1}{1-x}$，$\text{EGF}$ 的 $e^x$ 一样重要。
## 积性函数
若 $\forall \gcd(i,j)=1,f(i\times j)=f(i)\times f(j)$，则称数论函数 $f$ 为积性函数。
## 积性函数与 $\text{DGF}$
考虑将每个质数的贡献分开计算：
下文中 $\mathrm{Prime}$ 指全体质数集合。
### 单位函数 $\epsilon$
$$
1
$$
### 常数函数 $I$
$$
\begin{aligned}
\zeta(x)=&\prod\limits_{p\in \mathrm{Prime}}\sum\limits_{i=0}^\infin \frac{1}{p^{ix}}\\
=&\prod\limits_{p\in \mathrm{Prime}}\frac{1}{1-p^{-x}}
\end{aligned}
$$
### 莫比乌斯函数 $\mu$
$$
\begin{aligned}
&\prod\limits_{p\in\mathrm{Prime}}(1+\frac{-1}{p^x})\\
=&\prod\limits_{p\in\mathrm{Prime}}(1-p^{-x})\\
=&\frac{1}{\zeta(x)}
\end{aligned}
$$
### 刘维尔函数 $\lambda$
$$
\begin{aligned}
&\prod\limits_{p\in\mathrm{Prime}}\sum\limits_{i=0}^\infin\frac{(-1)^i}{p^{ix}}\\
=&\prod\limits_{p\in\mathrm{Prime}}\frac{1}{1+p^{-x}}\\
=&\frac{\zeta(2x)}{\zeta(x)}
\end{aligned}
$$
### $\mu^2$（点积）
$$
\begin{aligned}
&\prod\limits_{p\in\mathrm{Prime}}(1+\frac{1}{p^x})\\
=&\prod\limits_{p\in\mathrm{Prime}}(1+p^{-x})\\
=&\frac{\zeta(x)}{\zeta(2x)}
\end{aligned}
$$
### 恒等函数 $id_k$
$$
\begin{aligned}
&\sum\limits_{i=1}^\infin \frac{i^k}{i^x}\\
=&\sum\limits_{i=1}^\infin \frac{1}{i^{x-k}}\\
=&\zeta(x-k)
\end{aligned}
$$
### 欧拉函数 $\varphi$
$$
\begin{aligned}
&\prod\limits_{p\in\mathrm{Prime}}\left(1+\sum\limits_{i=1}^\infin\frac{p^i-p^{i-1}}{p^{ix}}\right)\\
=&\prod\limits_{p\in\mathrm{Prime}}\left(1+\sum\limits_{i=1}^\infin p^{i-ix}-\sum\limits_{i=1}^\infin p^{i-ix-1}\right)\\
=&\prod\limits_{p\in\mathrm{Prime}}\left(1+\frac{p^{1-x}}{1-p^{1-x}}-\frac{p^{-x}}{1-p^{1-x}}\right)\\
=&\prod\limits_{p\in\mathrm{Prime}}\frac{1-p^{-x}}{1-p^{1-x}}\\
=&\frac{\zeta(x-1)}{\zeta(x)}\\
\end{aligned}
$$
### 除数函数 $\sigma_k$
$$
\begin{aligned}
&\prod\limits_{p\in\mathrm{Prime}}\sum\limits_{i=0}^\infin\frac{\sum\limits_{j=0}^ip^{jk}}{p^{ix}}\\
=&\zeta(x)\zeta(x-k)
\end{aligned}
$$
关于这个的证明，等一会再说。
### 一个有趣的事实
已知 $\text{DGF}$ $F(x)$，该数论函数点积 $id_k$ 的 $\text{DGF}$ 为 $F(x-k)$，证明留给读者做练习。
## $\text{DGF}$ 的乘法
显然有，$(F*G)(x)=\sum\limits_{i=1}^\infin\frac{\sum\limits_{d\mid i}f_{d}g_{\frac{i}{d}}}{i^x}$，两个 $\text{DGF}$ 的乘积就是这两个数论函数狄利克雷卷积的 $\text{DGF}$。
我们可以通过这个做很多事，例如除数函数 $\text{DGF}$ 是 $\zeta(x)\zeta(x-k)$ 可以通过这个性质给出一个很简单的证明（$id_k*I=\sigma_k$）。
一些不那么显然的狄利克雷卷积可以被 $\text{DGF}$ 乘法轻松地证明：
注：$d=\sigma_0,\sigma=\sigma_1$。
$\frac{\zeta(x-1)}{\zeta(x)}\times\zeta(x)=\zeta(x-1)\Rightarrow\varphi*I=id$
$\frac{\zeta(x-1)}{\zeta(x)}\times\zeta(x)^2=\zeta(x)\zeta(x-1)\Rightarrow\varphi*d=\sigma$
直接卷积的复杂度为 $\mathrm O(n\log n)$。
```cpp
void mul(int const *f,int const *g,int *ans,int n){
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j+=i)
ans[j]+=f[i]*g[j/i];
}
```
## $\text{DGF}$ 的除法
已知数论函数 $F,G$，求 $H$ 使得 $F=H*G$。
$$
F_n=\sum\limits_{d\mid n}H_dG_{\frac{n}{d}}\\
H_nG_1=F_n-\sum\limits_{d\mid n\land d\ne n}H_dG_{\frac{n}{d}}
$$
求出 $H_n$ 后就枚举倍数更新即可。
```cpp
void div(int const *f,int const *g,int *ans,int n){
for(int i=1;i<=n;i++) ans[i]=f[i];
for(int i=1;i<=n;i++){
ans[i]/=g[1];
for(int j=i+i;j<=n;j+=i)
ans[j]-=ans[i]*g[j/i];
}
}
```
## $\text{DGF}$ 的求导与积分
$$
\frac{d\frac{f_n}{n^x}}{dx}=-\ln n\frac{f_n}{n^x}\\
\int\frac{f_n}{n^x}dx=-\frac{1}{\ln n}\frac{f_n}{n^x}+C
$$
$n=1$ 时特殊处理一下，这里使用质因子次数和的相反数作为 $\ln n$，它与 $\ln n$ 有着类似的性质，我们并不在意 $\ln n$ 的真实值，$\ln n$ 一定会被消掉，所以直接用质因子次数和的相反数代替即可。
```cpp
void der(int const *f,int *ans,int n){
for(int i=1;i<=n;i++) ans[i]=f[i]*c[i];
}
void inte(int const *f,int *ans,int n){
for(int i=1;i<=n;i++) ans[i]=f[i]/c[i];
}
```
## $\text{DGF}$ 的对数函数
$$
\ln(F(x))=\int\frac{F'(x)}{F(x)}dx
$$
```cpp
void ln(int const *f,int *ans,int n){
static int tmp[maxn];
der(f,tmp,n);
div(tmp,f,ans,n);
inte(ans,ans,n);
}
```
## $\text{DGF}$ 的指数函数
$$
\exp(F(x))=G(x)\\
G'(x)=F'(x)exp(F(x))=F'(x)G(x)\\
g_n\ln n=\sum\limits_{d\mid n}g_{\frac{n}{d}}f_d\ln d\\
$$
```cpp
void exp(int const *f,int *ans,int n){
static int tmp[maxn];
der(f,tmp,n);
for(int i=1;i<=n;i++)ans[i]=0;
ans[1]=1;
for(int i=1;i<=n;i++){
if(i!=1)ans[i]=1ll*ans[i]*pow(c[i],mod-2)%mod;
for(int j=i+i;j<=n;j+=i)
ans[j]=(ans[j]+1ll*ans[i]*tmp[j/i])%mod;
}
}
```
## [狄利克雷 k 次根 加强版](https://loj.ac/p/6713)
已知数论函数 $g$，求 $f$ 使得 $f^k=g$。
$$
f=\sqrt[k]{g}\\
F=\exp(\frac{\ln(G)}{k})
$$
代码：
```cpp
#include<cstdio>
int const mod=998244353;
int n,k,f[1000010],g[1000010],c[1000010];
int pow(int x,int y){
int res=1;
while(y){
if(y&1) res=1ll*x*res%mod;
x=1ll*x*x%mod;
y>>=1;
}
return res;
}
void div(int const *f,int const *g,int *ans,int n){
for(int i=1;i<=n;i++) ans[i]=f[i];
int inv=pow(g[1],mod-2);
for(int i=1;i<=n;i++){
ans[i]=1ll*ans[i]*inv%mod;
for(int j=i+i;j<=n;j+=i)
ans[j]=(ans[j]-1ll*ans[i]*g[j/i]%mod+mod)%mod;
}
}
void der(int const *f,int *ans,int n){
for(int i=1;i<=n;i++) ans[i]=1ll*f[i]*c[i]%mod;
}
void inte(int const *f,int *ans,int n){
for(int i=1;i<=n;i++) ans[i]=1ll*f[i]*pow(c[i],mod-2)%mod;
}
void ln(int const *f,int *ans,int n){
static int tmp[1000010];
der(f,tmp,n);
div(tmp,f,ans,n);
inte(ans,ans,n);
}
void exp(int const *f,int *ans,int n){
static int tmp[1000010];
der(f,tmp,n);
for(int i=1;i<=n;i++)ans[i]=0;
ans[1]=1;
for(int i=1;i<=n;i++){
if(i!=1)ans[i]=1ll*ans[i]*pow(c[i],mod-2)%mod;
for(int j=i+i;j<=n;j+=i)
ans[j]=(ans[j]+1ll*ans[i]*tmp[j/i])%mod;
}
}
int np[1000010],p[1000010],cnt;
int main(){
scanf("%d%d",&n,&k);
for(int i=2;i<=n;i++){
if(!np[i])p[++cnt]=i,c[i]=1;
for(int j=1;j<=cnt&&i*p[j]<=n;j++){
np[i*p[j]]=1,c[i*p[j]]=c[i]+1;
if(i%p[j]==0)break;
}
}
k=pow(k,mod-2);
for(int i=1;i<=n;i++)scanf("%d",f+i);
ln(f,g,n);
for(int i=1;i<=n;i++)g[i]=1ll*g[i]*k%mod;
exp(g,f,n);
for(int i=1;i<=n;i++)printf("%d ",f[i]);
return 0;
}
```
下面将介绍 $\text{DGF}$ 的用处。
## 构造杜教筛
先从几个简单的例子开始说起：
### [【模板】杜教筛](https://www.luogu.com.cn/problem/P4213)
$$
\varphi=\frac{\zeta(x-1)}{\zeta(x)}\\
\frac{\zeta(x-1)}{\zeta(x)}\times\zeta(x)=\zeta(x-1)\\
\Rightarrow \varphi*I=id
$$
$$
\mu=\frac{1}{\zeta(x)}\\
\frac{1}{\zeta(x)}\times\zeta(x)=1\\
\Rightarrow \mu*I=\epsilon
$$
看完这两个就应该能理解如何构造一个好的杜教筛了。
来点有难度的。
### [【模板】Min_25筛](https://www.luogu.com.cn/problem/P5325)
我们先尝试把这个东西的 $\text{DGF}$ 用 $\zeta$ 表示。
$$
\begin{aligned}
&\prod\limits_{p\in\mathrm{Prime}}\left(1+\sum\limits_{i=1}^\infin\frac{p^i(p^i-1)}{p^{ix}}\right)\\
=&\prod\limits_{p\in\mathrm{Prime}}\left(1+\sum\limits_{i=1}^\infin\frac{p^{2i}}{p^{ix}}-\sum\limits_{i=1}^\infin\frac{p^i}{p^{ix}}\right)\\
=&\prod\limits_{p\in\mathrm{Prime}}\left(1+\sum\limits_{i=1}^\infin p^{i(2-x)}-\sum\limits_{i=1}^\infin p^{i(1-x)}\right)\\
=&\prod\limits_{p\in\mathrm{Prime}}\left(1+\frac{p^{2-x}}{1-p^{2-x}}-\frac{p^{1-x}}{1-p^{1-x}}\right)\\
=&\prod\limits_{p\in\mathrm{Prime}}\frac{(1-p^{2-x})(1-p^{1-x})+p^{2-x}(1-p^{1-x})-p^{1-x}(1-p^{2-x})}{(1-p^{2-x})(1-p^{1-x})}\\
=&\prod\limits_{p\in\mathrm{Prime}}\frac{1-p^{1-x}-p^{2-x}+p^{3-2x}+p^{2-x}-p^{3-2x}-p^{1-x}+p^{3-2x}}{1-p^{1-x}-p^{2-x}+p^{3-2x}}\\
=&\prod\limits_{p\in\mathrm{Prime}}\frac{1-2p^{1-x}+p^{3-2x}}{1-p^{1-x}-p^{2-x}+p^{3-2x}}\\
=&\zeta(x-1)\zeta(x-2)\prod\limits_{p\in\mathrm{Prime}}(1-2p^{1-x}+p^{3-2x})\\
\end{aligned}
$$
我们发现后面那个东西似乎不能很好的用 $\zeta$ 表示，考虑换个方向推。
如果有一个积性函数的 $\text{DGF}$ 为 $\prod\limits_{p\in\mathrm{Prime}}(1+\sum\limits_{i=2}^\infin\frac{f(p^i)}{p^{ix}})$，那么我们是可以在 $\mathrm O(\sqrt n)$ 内求出它的前缀和的，因为 $[1,n]$ 之间的 $\text{Powerful Number}$（所有质因子次数都大于 $1$ 的数）只有 $\mathrm O(\sqrt n)$ 个。
证明：显然所有 $\text{Powerful Number}$ 都可以表示成 $a^2b^3$ 的形式。
$$
\begin{aligned}
&\mathrm O\left(\sum_{a=1}^{\sqrt n}\left(\frac{n}{a^2}\right)^{\frac{1}{3}}\right)\\
=&\mathrm O\left(\int_{1}^{\sqrt n}\left(\frac{n}{x^2}\right)^{\frac{1}{3}}dx\right)\\
=&\mathrm O(\sqrt n)\\
\end{aligned}
$$
我们现在想要把后面那个东西推成 $\prod\limits_{p\in\mathrm{Prime}}(1+\sum\limits_{i=2}^\infin\frac{f(p^i)}{p^{ix}})$ 的形式。
$$
\begin{aligned}
&\zeta(x-1)\zeta(x-2)\prod\limits_{p\in\mathrm{Prime}}(1-2p^{1-x}+p^{3-2x})\\
=&\zeta(x-1)\zeta(x-2)\prod_{p\in\mathrm{Prime}}(1-2p^{1-x}+p^{2(1-x)+1})\\
=&\zeta(x-1)\zeta(x-2)\prod_{p\in\mathrm{Prime}}((1-p^{1-x})^2+p^{2(1-x)+1}-p^{2(1-x)})\\
=&\frac{\zeta(x-2)}{\zeta(x-1)}\prod_{p\in\mathrm{Prime}}\frac{(1-p^{1-x})^2+p^{2(1-x)+1}-p^{2(1-x)}}{(1-p^{1-x})^2}\\
=&\frac{\zeta(x-2)}{\zeta(x-1)}\prod_{p\in\mathrm{Prime}}\left(1+\frac{p^{2(1-x)+1}}{(1-p^{1-x})^2}-\frac{p^{2(1-x)}}{(1-p^{1-x})^2}\right)\\
=&\frac{\zeta(x-2)}{\zeta(x-1)}\prod_{p\in\mathrm{Prime}}\left(1+\sum_{i=2}^\infin (i-1)p^{i(1-x)+1}-\sum_{i=2}^\infin (i-1)p^{i(1-x)}\right)\\
=&\frac{\zeta(x-2)}{\zeta(x-1)}\prod_{p\in\mathrm{Prime}}\left(1+\sum_{i=2}^\infin\frac{ip^{i+1}-p^{i+1}-ip^{i}+p^i}{p^{ix}}\right)\\
\end{aligned}
$$
设要求的函数为 $f$，$\frac{\zeta(x-2)}{\zeta(x-1)}$ 对应的函数为 $g$，$\prod\limits_{p\in\mathrm{Prime}}(1+\sum_{i=2}^\infin\frac{ip^{i+1}-p^{i+1}-ip^{i}+p^i}{p^{ix}})$ 对应的函数为 $h$。
则有 $f=g*h$，$g$ 可以直接杜教筛，至于杜教筛的构造，留给读者作为练习，$h$ 显然只在 $\text{Powerful Number}$ 处有值，直接爆搜所有小于 $\sqrt n$ 的质数即可，算到每一个 $\text{Powerful Number}$ 处统计 $h(x)(\sum\limits_{i=1}^{\lfloor\frac{n}{x}\rfloor} g(i))$ 即可求出 $\sum\limits_{i=1}^n f(i)$。
代码：
```cpp
#include<cstdio>
#include<cmath>
int const mod=1000000007,inv6=1000000008/6,inv2=1000000008/2;
int np[4641600],lim,cnt,p[464160],g[4641600],g2[4641600];
long long n;
int getsum(long long x){
if(x<=lim) return g[x];
if(g2[n/x]) return g2[n/x];
int ans=x%mod*((x+1)%mod)%mod*((2*x+1)%mod)%mod*inv6%mod;
for(long long l=2,r,d;l<=x;l=r+1){
r=x/(x/l);
ans=(ans-(l+r)%mod*(r-l+1)%mod*inv2%mod*getsum(x/l)%mod+mod)%mod;
}
return g2[n/x]=ans;
}
int ans;
void dfs(int k,long long m,int h){
if(k>cnt||m*p[k]>n||m*p[k]*p[k]>n){
long long const &p=n/m;
if(p<=lim)ans=(ans+1ll*h*g[p])%mod;
else ans=(ans+1ll*h*g2[n/p])%mod;
return;
}
long long p=1ll*::p[k]*::p[k];
dfs(k+1,m,h);
for(int e=2;m*p<=n;p*=::p[k],++e)dfs(k+1,m*p,p%mod*(::p[k]-1)%mod*(e-1)%mod*h%mod);
}
int main(){
scanf("%lld",&n);
lim=pow(n,2.0/3.0);if(!lim)++lim;
g[1]=1;
for(int i=2;i<=lim;i++){
if(!np[i])p[++cnt]=i,g[i]=i-1;
for(int j=1,tmp;j<=cnt&&(tmp=i*p[j])<=lim;j++){
np[tmp]=1;
if(i%p[j]==0){
g[tmp]=g[i]*p[j];
break;
}else g[tmp]=g[i]*g[p[j]];
}
}
for(int i=1;i<=lim;i++)g[i]=(g[i-1]+1ll*i*g[i])%mod;
getsum(n);
dfs(1,1,1);
printf("%d\n",ans);
return 0;
}
```
## 推通项
### [DETER2](https://www.luogu.com.cn/problem/SP1772)
容易发现，这道题在高斯消元完成后 $m'_{i,j}=\begin{cases}0 & i\nmid j \\\ f(i) & i\mid j\end{cases}$。
原因是只有 $i$ 的因数行会影响第 $i$ 行的值，而对于 $i\mid j$ 的 $j$，这些行的对应位置都相等。
而对于 $i\nmid j$ 的位置，因为 $\gcd(i,j)\mid i，\gcd(\gcd(i,j),j)=\gcd(i,j)$，所以在消元到第 $\gcd(i,j)$ 行时，$m_{i,j}=m_{\gcd(i,j),j}$，这样一减就变成 $0$ 了。
我们有 $m_{i,i}=\gcd(i,i)^k-\sum\limits_{d\mid i,d\ne i}m_{d,i}$ 即 $f(i)=i^k-\sum\limits_{d\mid i}f(d)$，也就是 $\sum\limits_{d\mid i}f(i)=id_k(i)$，到这一步写个狄利克雷除法就可以 $O(n\log n)$ 的做了。
但根据数据范围看，我们应该需要 $O(n)$ 的解法，所以继续推，设 $f$ 的 DGF 为 $F(x)$，我们已知 $1$ 的 DGF 为 $\zeta(x)$，$id_k$ 的 DGF 为 $\zeta(x-k)$，所以 $F(x)\zeta(x)=\zeta(x-k)$，$F(x)=\frac{\zeta(x-k)}{\zeta(x)}$，事实上，$k=1$ 时 $f$ 就是 $\varphi$。
$$
\begin{aligned}
F(x)=&\frac{\zeta(x-k)}{\zeta(x)}\\
=&\prod\limits_{p\in \mathrm{Prime}} \frac{1-p^{-x}}{1-p^{-x+k}}\\
=&\prod\limits_{p\in \mathrm{Prime}}\left(1+\sum\limits_{i=1}^\infin\frac{p^{ik}-p^{(i-1)k}}{p^{ix}}\right)
\end{aligned}
$$
所以 $f$ 在素数幂 $p^i$ 处的取值为 $p^{ik}-p^{(i-1)k}$，线性筛即可。
答案即为 $\prod\limits_{i=1}^nf(i)$。
```cpp
#include<cstdio>
int pw[1000010],f[1000010],t,n,k,np[1000010],p[1000010];
int const mod=1e6+3;
int fpow(int x,int y){
int res=1;
while(y){
if(y&1)res=1ll*res*x%mod;
x=1ll*x*x%mod;
y>>=1;
}
return res;
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&k);
f[1]=1;
int ans=1,cnt=0;
for(int i=2;i<=n;i++){
if(!np[i])p[++cnt]=i,f[i]=(mod+(pw[i]=fpow(i,k))-1)%mod;
for(int j=1;j<=cnt&&p[j]*i<=n;j++){
np[i*p[j]]=1;
if(i%p[j]) f[i*p[j]]=1ll*f[i]*f[p[j]]%mod;
else{f[i*p[j]]=1ll*f[i]*pw[p[j]]%mod;break;}
}
ans=1ll*ans*f[i]%mod;
}
printf("%d\n",ans);
}
return 0;
}
```