26 Jan 2021 11378字 38分 186次 数学 and 数论
如果这篇博客帮助到你,可以请我喝一杯咖啡~
CC BY-NC-SA 4.0 (除特别声明或转载文章外) 狄利克雷生成函数(DGF)浅谈
前置知识:无。
数论函数
定义域为正整数,陪域为复数的函数。
狄利克雷卷积
对于数论函数 f,g,定义它们的狄利克雷卷积为 (f∗g)(x)=d∣x∑f(d)g(dx)。
换种容易理解的表示方式即 (f∗g)(x)=a×b=x∑f(a)g(b)。
狄利克雷生成函数(DGF)
数论函数 f 在 i 处的点值表示为 fi,则 f 的狄利克雷生成函数 F(x)=i=1∑∞ixfi。
黎曼 ζ 函数
ζ(x)=i=1∑∞ix1,容易发现,这是常数函数 I(x)=1 的 DGF。
这个函数与 OGF 的 1−x1,EGF 的 ex 一样重要。
积性函数
若 ∀gcd(i,j)=1,f(i×j)=f(i)×f(j),则称数论函数 f 为积性函数。
积性函数与 DGF
考虑将每个质数的贡献分开计算:
下文中 Prime 指全体质数集合。
单位函数 ϵ
1常数函数 I
ζ(x)==p∈Prime∏i=0∑∞pix1p∈Prime∏1−p−x1莫比乌斯函数 μ
==p∈Prime∏(1+px−1)p∈Prime∏(1−p−x)ζ(x)1刘维尔函数 λ
==p∈Prime∏i=0∑∞pix(−1)ip∈Prime∏1+p−x1ζ(x)ζ(2x)μ2(点积)
==p∈Prime∏(1+px1)p∈Prime∏(1+p−x)ζ(2x)ζ(x)
恒等函数 idk
==i=1∑∞ixiki=1∑∞ix−k1ζ(x−k)欧拉函数 φ
====p∈Prime∏(1+i=1∑∞pixpi−pi−1)p∈Prime∏(1+i=1∑∞pi−ix−i=1∑∞pi−ix−1)p∈Prime∏(1+1−p1−xp1−x−1−p1−xp−x)p∈Prime∏1−p1−x1−p−xζ(x)ζ(x−1)除数函数 σk
=p∈Prime∏i=0∑∞pixj=0∑ipjkζ(x)ζ(x−k)关于这个的证明,等一会再说。
一个有趣的事实
已知 DGF F(x),该数论函数点积 idk 的 DGF 为 F(x−k),证明留给读者做练习。
DGF 的乘法
显然有,(F∗G)(x)=i=1∑∞ixd∣i∑fdgdi,两个 DGF 的乘积就是这两个数论函数狄利克雷卷积的 DGF。
我们可以通过这个做很多事,例如除数函数 DGF 是 ζ(x)ζ(x−k) 可以通过这个性质给出一个很简单的证明(idk∗I=σk)。
一些不那么显然的狄利克雷卷积可以被 DGF 乘法轻松地证明:
注:d=σ0,σ=σ1。
ζ(x)ζ(x−1)×ζ(x)=ζ(x−1)⇒φ∗I=id
ζ(x)ζ(x−1)×ζ(x)2=ζ(x)ζ(x−1)⇒φ∗d=σ
直接卷积的复杂度为 O(nlogn)。
DGF 的除法
已知数论函数 F,G,求 H 使得 F=H∗G。 Fn=d∣n∑HdGdnHnG1=Fn−d∣n∧d=n∑HdGdn 求出 Hn 后就枚举倍数更新即可。
DGF 的求导与积分
dxdnxfn=−lnnnxfn∫nxfndx=−lnn1nxfn+C
n=1 时特殊处理一下,这里使用质因子次数和的相反数作为 lnn,它与 lnn 有着类似的性质,我们并不在意 lnn 的真实值,lnn 一定会被消掉,所以直接用质因子次数和的相反数代替即可。
DGF 的对数函数
ln(F(x))=∫F(x)F′(x)dxDGF 的指数函数
exp(F(x))=G(x)G′(x)=F′(x)exp(F(x))=F′(x)G(x)gnlnn=d∣n∑gdnfdlnd已知数论函数 g,求 f 使得 fk=g。 f=kgF=exp(kln(G)) 代码:
#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;
}
下面将介绍 DGF 的用处。
构造杜教筛
先从几个简单的例子开始说起:
φ=ζ(x)ζ(x−1)ζ(x)ζ(x−1)×ζ(x)=ζ(x−1)⇒φ∗I=id μ=ζ(x)1ζ(x)1×ζ(x)=1⇒μ∗I=ϵ看完这两个就应该能理解如何构造一个好的杜教筛了。
来点有难度的。
我们先尝试把这个东西的 DGF 用 ζ 表示。
=======p∈Prime∏(1+i=1∑∞pixpi(pi−1))p∈Prime∏(1+i=1∑∞pixp2i−i=1∑∞pixpi)p∈Prime∏(1+i=1∑∞pi(2−x)−i=1∑∞pi(1−x))p∈Prime∏(1+1−p2−xp2−x−1−p1−xp1−x)p∈Prime∏(1−p2−x)(1−p1−x)(1−p2−x)(1−p1−x)+p2−x(1−p1−x)−p1−x(1−p2−x)p∈Prime∏1−p1−x−p2−x+p3−2x1−p1−x−p2−x+p3−2x+p2−x−p3−2x−p1−x+p3−2xp∈Prime∏1−p1−x−p2−x+p3−2x1−2p1−x+p3−2xζ(x−1)ζ(x−2)p∈Prime∏(1−2p1−x+p3−2x)我们发现后面那个东西似乎不能很好的用 ζ 表示,考虑换个方向推。
如果有一个积性函数的 DGF 为 p∈Prime∏(1+i=2∑∞pixf(pi)),那么我们是可以在 O(n) 内求出它的前缀和的,因为 [1,n] 之间的 Powerful Number(所有质因子次数都大于 1 的数)只有 O(n) 个。
证明:显然所有 Powerful Number 都可以表示成 a2b3 的形式。
==O⎝⎛a=1∑n(a2n)31⎠⎞O(∫1n(x2n)31dx)O(n)我们现在想要把后面那个东西推成 p∈Prime∏(1+i=2∑∞pixf(pi)) 的形式。
======ζ(x−1)ζ(x−2)p∈Prime∏(1−2p1−x+p3−2x)ζ(x−1)ζ(x−2)p∈Prime∏(1−2p1−x+p2(1−x)+1)ζ(x−1)ζ(x−2)p∈Prime∏((1−p1−x)2+p2(1−x)+1−p2(1−x))ζ(x−1)ζ(x−2)p∈Prime∏(1−p1−x)2(1−p1−x)2+p2(1−x)+1−p2(1−x)ζ(x−1)ζ(x−2)p∈Prime∏(1+(1−p1−x)2p2(1−x)+1−(1−p1−x)2p2(1−x))ζ(x−1)ζ(x−2)p∈Prime∏(1+i=2∑∞(i−1)pi(1−x)+1−i=2∑∞(i−1)pi(1−x))ζ(x−1)ζ(x−2)p∈Prime∏(1+i=2∑∞pixipi+1−pi+1−ipi+pi)设要求的函数为 f,ζ(x−1)ζ(x−2) 对应的函数为 g,p∈Prime∏(1+∑i=2∞pixipi+1−pi+1−ipi+pi) 对应的函数为 h。
则有 f=g∗h,g 可以直接杜教筛,至于杜教筛的构造,留给读者作为练习,h 显然只在 Powerful Number 处有值,直接爆搜所有小于 n 的质数即可,算到每一个 Powerful Number 处统计 h(x)(i=1∑⌊xn⌋g(i)) 即可求出 i=1∑nf(i)。
代码:
推通项
容易发现,这道题在高斯消元完成后 m’i,j={0f(i)i∤ji∣j。
原因是只有 i 的因数行会影响第 i 行的值,而对于 i∣j 的 j,这些行的对应位置都相等。
而对于 i∤j 的位置,因为 gcd(i,j)∣i,gcd(gcd(i,j),j)=gcd(i,j),所以在消元到第 gcd(i,j) 行时,mi,j=mgcd(i,j),j,这样一减就变成 0 了。
我们有 mi,i=gcd(i,i)k−d∣i,d=i∑md,i 即 f(i)=ik−d∣i∑f(d),也就是 d∣i∑f(i)=idk(i),到这一步写个狄利克雷除法就可以 O(nlogn) 的做了。
但根据数据范围看,我们应该需要 O(n) 的解法,所以继续推,设 f 的 DGF 为 F(x),我们已知 1 的 DGF 为 ζ(x),idk 的 DGF 为 ζ(x−k),所以 F(x)ζ(x)=ζ(x−k),F(x)=ζ(x)ζ(x−k),事实上,k=1 时 f 就是 φ。
F(x)===ζ(x)ζ(x−k)p∈Prime∏1−p−x+k1−p−xp∈Prime∏(1+i=1∑∞pixpik−p(i−1)k)所以 f 在素数幂 pi 处的取值为 pik−p(i−1)k,线性筛即可。
答案即为 i=1∏nf(i)。