狄利克雷生成函数（ $\text{DGF}$ ）浅谈

前置知识：无。

数论函数

定义域为正整数，陪域为复数的函数。

狄利克雷卷积

对于数论函数

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 次根加强版

已知数论函数

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}

的用处。

构造杜教筛

先从几个简单的例子开始说起：

【模板】杜教筛

\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筛

我们先尝试把这个东西的

\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

容易发现，这道题在高斯消元完成后

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;
}

狄利克雷生成函数浅谈

文章操作

狄利克雷生成函数（ $\text{DGF}$ ）浅谈

数论函数

狄利克雷卷积

狄利克雷生成函数（ $\text{DGF}$ ）

黎曼 $\zeta$ 函数

积性函数

积性函数与 $\text{DGF}$

单位函数 $\epsilon$

常数函数 $I$

莫比乌斯函数 $\mu$

刘维尔函数 $\lambda$

$\mu^2$ （点积）

恒等函数 $id_k$

欧拉函数 $\varphi$

除数函数 $\sigma_k$

一个有趣的事实

$\text{DGF}$ 的乘法

$\text{DGF}$ 的除法

$\text{DGF}$ 的求导与积分

$\text{DGF}$ 的对数函数

$\text{DGF}$ 的指数函数

狄利克雷 k 次根加强版

构造杜教筛

【模板】杜教筛

【模板】Min_25筛

推通项

DETER2

相关推荐

评论

狄利克雷生成函数浅谈

文章操作

狄利克雷生成函数（DGF\text{DGF}DGF）浅谈

数论函数

狄利克雷卷积

狄利克雷生成函数（DGF\text{DGF}DGF）

黎曼 ζ\zetaζ 函数

积性函数

积性函数与 DGF\text{DGF}DGF

单位函数 ϵ\epsilonϵ

常数函数 III

莫比乌斯函数 μ\muμ

刘维尔函数 λ\lambdaλ

μ2\mu^2μ2（点积）

恒等函数 idkid_kidk​

欧拉函数 φ\varphiφ

除数函数 σk\sigma_kσk​

一个有趣的事实

DGF\text{DGF}DGF 的乘法

DGF\text{DGF}DGF 的除法

DGF\text{DGF}DGF 的求导与积分

DGF\text{DGF}DGF 的对数函数

DGF\text{DGF}DGF 的指数函数

狄利克雷 k 次根 加强版

构造杜教筛

【模板】杜教筛

【模板】Min_25筛

推通项

DETER2

相关推荐

评论

狄利克雷生成函数（ $\text{DGF}$ ）浅谈

狄利克雷生成函数（ $\text{DGF}$ ）

黎曼 $\zeta$ 函数

积性函数与 $\text{DGF}$

单位函数 $\epsilon$

常数函数 $I$

莫比乌斯函数 $\mu$

刘维尔函数 $\lambda$

$\mu^2$ （点积）

恒等函数 $id_k$

欧拉函数 $\varphi$

除数函数 $\sigma_k$

$\text{DGF}$ 的乘法

$\text{DGF}$ 的除法

$\text{DGF}$ 的求导与积分

$\text{DGF}$ 的对数函数

$\text{DGF}$ 的指数函数

狄利克雷 k 次根加强版