杜教筛

杜教筛用于求解积性函数的前缀和。

定义函数:ϵ(i)=[i=1],I(i)=1,id(i)=i\epsilon(i)=[i=1],I(i)=1,id(i)=i

狄利克雷卷积

(fg)(n)=f(n)g(n)=ij=nf(i)g(j)(f*g)(n)=f(n)*g(n)=\sum\limits_{ij=n} f(i)g(j)

  1. 交换律:fg=gff*g=g*f,显然。

  2. 结合律:(fg)h=f(gh)(f*g)*h=f*(g*h)

    结合律证明:

    ((fg)h)(n)=ij=n(fg)(i)h(j)=ij=n(pq=if(p)g(q))h(j)=ijk=nf(i)g(j)h(k)((f*g)*h)(n)=\sum\limits_{ij=n}(f*g)(i)h(j)=\sum\limits_{ij=n}(\sum\limits_{pq=i}f(p)g(q))h(j)=\sum\limits_{ijk=n}f(i)g(j)h(k)

    (f(gh))(n)=ij=nf(i)(gh)(j)=ij=nf(i)(pq=jg(p)h(q))=ijk=nf(i)g(j)h(k)(f*(g*h))(n)=\sum\limits_{ij=n}f(i)(g*h)(j)=\sum\limits_{ij=n}f(i)(\sum\limits_{pq=j}g(p)h(q))=\sum\limits_{ijk=n}f(i)g(j)h(k)

  3. 单位元:ϵ\epsilonϵf=f\epsilon*f=f

    (ϵf)(n)=ij=nϵ(i)f(j)=f(n)(\epsilon*f)(n)=\sum\limits_{ij=n}\epsilon(i)f(j)=f(n)

    ϵf=f\epsilon*f=f

莫比乌斯函数

II 在狄利克雷卷积意义下的逆元为莫比乌斯函数 μ\mu

由狄利克雷卷积的定义式得:Iμ=ϵdnμ(d)=ϵ(n)I*\mu=\epsilon\Rightarrow\sum\limits_{d|n}\mu(d)=\epsilon(n)

因此,得到:μ(n)={1,n=1(1)k,n能写成k个不同质数之积0,n有完全平方数因子\mu(n)=\begin{cases} 1, & n=1\\ (-1)^k, & n\text{能写成}k\text{个不同质数之积}\\ 0, & n\text{有完全平方数因子} \end{cases}

证明:

  1. n=1n=1 时,μ(1)=ϵ(1)=1\mu(1)=\epsilon(1)=1

  2. n1n\neq 1 时,由唯一分解定理得:n=p1a1p2a2p3a3pkakn=p_1^{a_1}p_2^{a_2}p_3^{a_3}\dots p_k^{a_k}

    dnμ(d)=μ(1)+μ(p1)+μ(p2)+μ(p3)++μ(pk)+μ(p1p2)++μ(p1p2p3pk)\sum\limits_{d|n}\mu(d)=\mu(1)+\mu(p_1)+\mu(p_2)+\mu(p_3)+\dots+\mu(p_k)+\mu(p_1p_2)+\dots+\mu(p_1p_2p_3\dots p_k)

    dnμ(d)=i=0kCki(1)i=0\Rightarrow \sum\limits_{d|n}\mu(d)=\sum\limits_{i=0}^k C_k^i(-1)^i=0

部分函数的狄利克雷卷积性质

  1. Iμ=ϵI*\mu=\epsilon

    证明见莫比乌斯函数部分。

  2. φI=id\varphi*I=id

    证明:要证 φI=id\varphi*I=id,只需证 dnφ(d)=n\sum\limits_{d|n}\varphi(d)=n

    f(n)=dnφ(d)f(n)=\sum\limits_{d|n}\varphi(d)。则若 n,mn,m 互质,则 f(nm)=dnmφ(d)=(dnφ(d))(dmφ(m))=f(n)f(m)f(nm)=\sum\limits_{d|nm}\varphi(d)=(\sum\limits_{d|n}\varphi(d))(\sum\limits_{d|m}\varphi(m))=f(n)f(m)

    因此 ff 是积性函数。

    f(pa)=dpaφ(d)=φ(1)+φ(p)+φ(p2)++φ(pa)=paf(p^a)=\sum\limits_{d|p^a}\varphi(d)=\varphi(1)+\varphi(p)+\varphi(p^2)+\dots+\varphi(p^a)=p^a

    n=p1a1p2a2p3a3pkakn=p_1^{a_1}p_2^{a_2}p_3^{a_3}\dots p_k^{a_k},则 f(n)=i=1kf(piai)=i=1kpiai=nf(n)=\prod\limits_{i=1}^k f(p_i^{a_i})=\prod\limits_{i=1}^kp_i^{a_i}=n。故dnφ(d)=n\sum\limits_{d|n}\varphi(d)=n

  3. μid=φ\mu*id=\varphi

    由性质 1 与 2,得 Iμid=ϵφII*\mu*id=\epsilon*\varphi*I,故 μid=ϵφ=φ\mu*id=\epsilon*\varphi=\varphi

莫比乌斯反演

f(n)=dng(d)=dng(nd)f(n)=\sum\limits_{d|n}g(d)=\sum\limits_{d|n}g(\frac{n}{d}),则有 g(n)=dnμ(d)f(nd)=dnμ(nd)f(d)g(n)=\sum\limits_{d|n}\mu(d)f(\frac{n}{d})=\sum\limits_{d|n}\mu(\frac{n}{d})f(d)

证明:原命题等价于 f=gIg=fμf=g*I \Leftrightarrow g=f*\mu

f=gIfμ=(gI)μfμ=g(Iμ)fu=gϵfμ=gf=g*I\Rightarrow f*\mu=(g*I)*\mu\Rightarrow f*\mu=g*(I*\mu)\Rightarrow f*u=g*\epsilon\Rightarrow f*\mu=g

反之亦然。

杜教筛

S(n)=i=1nf(i)S(n)=\sum\limits_{i=1}^nf(i),注意 ff 为积性函数。

寻找另一个合适的积性函数 gg,得到 i=1n(fg)(i)=i=1npq=if(p)g(q)=i=1ndif(d)g(nd)=d=1ng(d)i=1ndf(i)=d=1ng(d)S(nd)\sum\limits_{i=1}^n(f*g)(i)=\sum\limits_{i=1}^n\sum\limits_{pq=i}f(p)g(q)=\sum\limits_{i=1}^n\sum\limits_{d|i}f(d)g(\frac{n}{d})=\sum\limits_{d=1}^ng(d)\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}f(i)=\sum\limits_{d=1}^ng(d)S(\left\lfloor\frac{n}{d}\rfloor\right)

S(n)g(1)=i=1n(fg)(i)i=2ng(i)S(ni)S(n)g(1)=\sum\limits_{i=1}^n(f*g)(i)-\sum\limits_{i=2}^ng(i)S(\left\lfloor\frac{n}{i}\rfloor\right)

若能快速求解 fgf*g 的前缀和与 gg 的前缀和,则用数论分块的方法即可在 O(n34)O(n^{\frac{3}{4}}) 复杂度内求解 ff 的前缀和。

复杂度证明:令 T(n)T(n) 为求解 S(n)S(n) 的复杂度。

T(n)=i=1n(T(ni)+T(i))T(n)=\sum\limits_{i=1}^{\sqrt n}(T(\frac{n}{i})+T(i))。前半部分为递归求解复杂度,后半部分为数论分块复杂度。

可以认为 T(n)=i=1n(i+ni)T(n)=\sum\limits_{i=1}^{\sqrt n}(\sqrt i+\sqrt{\frac{n}{i}}),显然 inii\le \frac{n}{i},故忽略 i\sqrt i 的项,得到 T(n)=i=1nni1nnx=2nn=O(n34)T(n)=\sum\limits_{i=1}^{\sqrt n} \sqrt{\frac{n}{i}}\le\int_1^{\sqrt n} \frac{\sqrt{n}}{\sqrt{x}}=2\sqrt n\sqrt{\sqrt n}=O(n^{\frac{3}{4}})

为降低杜教筛复杂度,我们先用线性筛预处理前 ntn^t 个函数前缀和值,积分式变为:1n1tnx=O(n10.5t)\int_1^{n^{1-t}}\frac{\sqrt{n}}{\sqrt{x}}=O(n^{1-0.5t})

nt=n10.5tn^t=n^{1-0.5t} 时复杂度最优,则 t=23t=\frac{2}{3},杜教筛复杂度为 O(n23)O(n^{\frac{2}{3}})