杜教筛
杜教筛用于求解积性函数的前缀和。
定义函数:ϵ(i)=[i=1],I(i)=1,id(i)=i。
狄利克雷卷积
(f∗g)(n)=f(n)∗g(n)=ij=n∑f(i)g(j)
-
交换律:f∗g=g∗f,显然。
-
结合律:(f∗g)∗h=f∗(g∗h)。
结合律证明:
((f∗g)∗h)(n)=ij=n∑(f∗g)(i)h(j)=ij=n∑(pq=i∑f(p)g(q))h(j)=ijk=n∑f(i)g(j)h(k)
(f∗(g∗h))(n)=ij=n∑f(i)(g∗h)(j)=ij=n∑f(i)(pq=j∑g(p)h(q))=ijk=n∑f(i)g(j)h(k)
-
单位元:ϵ ,ϵ∗f=f。
(ϵ∗f)(n)=ij=n∑ϵ(i)f(j)=f(n)
故 ϵ∗f=f。
莫比乌斯函数
称 I 在狄利克雷卷积意义下的逆元为莫比乌斯函数 μ。
由狄利克雷卷积的定义式得:I∗μ=ϵ⇒d∣n∑μ(d)=ϵ(n)。
因此,得到:μ(n)=⎩⎪⎪⎨⎪⎪⎧1,(−1)k,0,n=1n能写成k个不同质数之积n有完全平方数因子
证明:
-
当 n=1 时,μ(1)=ϵ(1)=1。
-
当 n=1 时,由唯一分解定理得:n=p1a1p2a2p3a3…pkak。
d∣n∑μ(d)=μ(1)+μ(p1)+μ(p2)+μ(p3)+⋯+μ(pk)+μ(p1p2)+⋯+μ(p1p2p3…pk)
⇒d∣n∑μ(d)=i=0∑kCki(−1)i=0。
部分函数的狄利克雷卷积性质
-
I∗μ=ϵ。
证明见莫比乌斯函数部分。
-
φ∗I=id。
证明:要证 φ∗I=id,只需证 d∣n∑φ(d)=n。
设 f(n)=d∣n∑φ(d)。则若 n,m 互质,则 f(nm)=d∣nm∑φ(d)=(d∣n∑φ(d))(d∣m∑φ(m))=f(n)f(m)。
因此 f 是积性函数。
f(pa)=d∣pa∑φ(d)=φ(1)+φ(p)+φ(p2)+⋯+φ(pa)=pa。
令 n=p1a1p2a2p3a3…pkak,则 f(n)=i=1∏kf(piai)=i=1∏kpiai=n。故d∣n∑φ(d)=n。
-
μ∗id=φ。
由性质 1 与 2,得 I∗μ∗id=ϵ∗φ∗I,故 μ∗id=ϵ∗φ=φ。
莫比乌斯反演
若 f(n)=d∣n∑g(d)=d∣n∑g(dn),则有 g(n)=d∣n∑μ(d)f(dn)=d∣n∑μ(dn)f(d)。
证明:原命题等价于 f=g∗I⇔g=f∗μ。
f=g∗I⇒f∗μ=(g∗I)∗μ⇒f∗μ=g∗(I∗μ)⇒f∗u=g∗ϵ⇒f∗μ=g
反之亦然。
杜教筛
令 S(n)=i=1∑nf(i),注意 f 为积性函数。
寻找另一个合适的积性函数 g,得到 i=1∑n(f∗g)(i)=i=1∑npq=i∑f(p)g(q)=i=1∑nd∣i∑f(d)g(dn)=d=1∑ng(d)i=1∑⌊dn⌋f(i)=d=1∑ng(d)S(⌊dn⌋)。
则 S(n)g(1)=i=1∑n(f∗g)(i)−i=2∑ng(i)S(⌊in⌋)。
若能快速求解 f∗g 的前缀和与 g 的前缀和,则用数论分块的方法即可在 O(n43) 复杂度内求解 f 的前缀和。
复杂度证明:令 T(n) 为求解 S(n) 的复杂度。
T(n)=i=1∑n(T(in)+T(i))。前半部分为递归求解复杂度,后半部分为数论分块复杂度。
可以认为 T(n)=i=1∑n(i+in),显然 i≤in,故忽略 i 的项,得到 T(n)=i=1∑nin≤∫1nxn=2nn=O(n43)。
为降低杜教筛复杂度,我们先用线性筛预处理前 nt 个函数前缀和值,积分式变为:∫1n1−txn=O(n1−0.5t)。
当 nt=n1−0.5t 时复杂度最优,则 t=32,杜教筛复杂度为 O(n32)。