狄利克雷生成函数是数论中的一项重要工具，与 ( ext{OI}) 也是一个不可分割的存在，能将一些数论式子推向本质，且能很好地构造筛法。
注：以下讨论若无特殊说明 (p) 代表一个质数，( ext{Prime}) 代表全体质数集。
(1.) 狄利克雷生成函数初步
( ext{Part 1}) 定义与基本定理
一般的，我们如下定义一个数论函数 (f) 的狄利克雷生成函数，简称 ( ext{dgf})：
(F(z)=sumlimits_{ngeq 1}dfrac{f(n)}{n^z}) ，通常有 (f(1)=1)
与其他生成函数一样，取系数得到一般项是其主要目的之一，可记作 (f(n)=[n^{-z}]F(z))
而耳熟能详的狄利克雷卷积，同其他生成函数一样，是两个狄利克雷生成函数的积。
若设 (G(z)=sumlimits_{ngeq 1}dfrac{g(n)}{n^z}) 则 (f) 与 (g) 的卷积就是 (F(z) imes G(z)=H(z))
同样设 (H(z)=sumlimits_{ngeq 1}dfrac{h(n)}{n^z}) ，则有 (h(n)=sumlimits_{d|n}f(d)g(n/d)) 。 (cdotscdots(1.1.1))
这是因为 (F,G) 中的一项 (dfrac{f(n)}{n^z},dfrac{g(m)}{m^z}) 之积 (dfrac{f(n)g(m)}{(nm)^z}) 能贡献到 (dfrac{h(nm)}{(nm)^z}) 中。
还有一个显而易见的性质：
若 (f(n)) 的 ( ext{dgf}) 是 (F(z)) ，则 (n^tf(n)) 的 ( ext{dgf}) 是 (F(z-t)) 。 (cdotscdots(1.1.2))
因为 (sumlimits_{ngeq 1}dfrac{n^tf(n)}{n^z}=sumlimits_{ngeq 1}dfrac{f(n)}{n^{z-t}}=F(z-t))
接下来是狄利克雷生成函数的最本质也最有用的性质：
若 (f) 为积性函数，即 (forall ij=n,gcd(i,j)=1,f(n)=f(i)f(j))
则 (F(z)=sumlimits_{ngeq 1}dfrac{f(n)}{n^z}=prodlimits_{pin ext{Prime}}1+frac{f(p)}{p^z}+frac{f(p^2)}{p^{2z}}+frac{f(p^3)}{p^{3z}}+dots=prodlimits_{pin ext{Prime}}sumlimits_{kgeq 0}dfrac{f(p^k)}{p^{kz}}cdotscdots(1.1.3))
证明：
从右往左推，对每个质数每一个的 (dfrac{f(p^k)}{p^{kz}}) 都能与其他一些质数的这种项乘其来得出 (dfrac{f(p_1^{alpha_1})f(p_2^{alpha_2})dots f(p_k^{alpha_k})}{p_1^{alpha_1z}p_2^{alpha_2z}dots p_k^{alpha_kz}}=dfrac{f(p_1^{alpha_1}p_2^{alpha_2}dots p_k^{alpha_k})}{(p_1^{alpha_1}p_2^{alpha_2}dots p_k^{alpha_k})^z}) 。由唯一分解定理可得出所有正整数 (n) 的 (dfrac{f(n)}{n^z}) 将不重不漏地出现，求和后就是 (F(z)) 。
观察一下最后一个等号，会发现对每个 (p) ，(dfrac{1}{p^z}) 固定不变，所以有时会设其为 (x) ，再对每个 (p) 写成关于 (x) 的级数 (f_p(x)=sumlimits_{kgeq 0}f(p^k)x^k) ，称之为贝尔级数，本质上就是是狄利克雷生成函数的衍生，二者相互依存。
( ext{Part 2}) 简单的运用
(1.) (f(n)=1)
如果将 (f(n)=1) 带入其狄利克雷生成函数，得到 (F(z)=sumlimits_{ngeq 1}dfrac{1}{n^z}=zeta(z))
这就是黎曼 (zeta) 函数，它将在接下来的运用中发挥重要作用。
由于 (f(n)=1) 满足积性函数的定义，所以可用 ((1.1.3)) 改写：
(F(z)=sumlimits_{ngeq 1}{dfrac{1}{n^z}}=prodlimits_{pin ext{Prime}}sumlimits_{kgeq 0}dfrac{1}{p^{kz}}=prodlimits_{pin ext{Prime}}sumlimits_{kgeq 0}(p^{-z})^k=prodlimits_{pin ext{Prime}}dfrac{1}{1-p^{-z}}cdotscdots(1.2.1))
(2.) (f(n)=mu(n))
由于 (mu(n)) 为积性函数，所以可以直接用 ((1.1.3)) 展开。
所以只用看对每个 (p^k) ，(mu(p^k)) 的值。
(mu(p^k)=egin{cases}1,k=0\-1,k=1\0,kgeq 2end{cases})
所以 (F(z)=prodlimits_{pin ext{Prime}}sumlimits_{kgeq 0}dfrac{mu(p^k)}{p^{kz}}=prodlimits_{pin ext{Prime}}1+dfrac{-1}{p^z}=prodlimits_{pin ext{Prime}}1-p^{-z}=dfrac{1}{zeta(z)}cdotscdots(1.2.2))
如果把右侧的 (zeta(z)) 乘到左边，得到 (F(z)zeta(z)=1) 。
取两边 (n^{-z}) 的系数，那 (F(z)zeta(z)) 就是两个 ( ext{dgf}) 的卷积，而右边仅在 (n=1) 时值为 (1) 。
所以 (sumlimits_{d|n}mu(d) imes1=sumlimits_{d|n}mu(d)=[n=1]cdotscdots(1.2.3))
有了莫比乌斯函数的 ( ext{dgf}) ，我们将揭示莫比乌斯反演的本质。
莫反的原式如下 (g(n)=sumlimits_{d|n}f(d)Leftrightarrow f(n)=sumlimits_{d|n}g(d)mu(n/d)cdotscdots(1.2.4))
事实上由于卷积， (g(n)=sumlimits_{d|n}f(d)) 可看做 (G(z)=F(z)zeta(z)) ，两边 (n^{-z}) 的系数。
那把右边 (zeta(z)) 除到左边，得到 (G(z)dfrac{1}{zeta(z)}=F(z))
而莫比乌斯函数的 ( ext{dgf}) 就是 (dfrac{1}{zeta(z)}) ，所以 (G(z)dfrac{1}{zeta(z)}) 就是 (g) 与 (mu) 的卷积。
再取两边 (n^{-z}) 的系数就能得到 (sumlimits_{d|n}g(d)mu(n/d)=f(n))
其实 ((1.2.3)) 仅是 ((1.2.4)) 的一个特例。
(3.) (f(n)=varphi(n))
其中 (varphi(n)) 是欧拉 (varphi) 函数，代表 (n) 以内与 (n) 互质的数的个数。
而 (varphi(n)=nsumlimits_{p|n,pin ext{Prime}}1-dfrac{1}{p}) ，所以 (varphi) 仍是一个积性函数。
为了求其 ( ext{dgf}) 我们依然想得知 (varphi(p^k)) 的值：
(varphi(p^k)=egin{cases}1,k=0\left(1-frac{1}{p} ight)p^k,kgeq 1end{cases})
所以
因为 (dfrac{zeta(z-1)}{zeta(z)}=zeta(z-1)dfrac{1}{zeta(z)}) 是两个 ( ext{dgf}) 的卷积。
而由 ((1.1.2)) (zeta(z-1)) 是 (n) 的 ( ext{dgf}) ，(dfrac{1}{zeta(z)}) 是 (mu(n)) 的 ( ext{dgf})
所以 ([n^{-z}]dfrac{zeta(z-1)}{zeta(z)}=sumlimits_{d|n}dmu(n/d))
而 ([n^{-z}]dfrac{zeta(z-1)}{zeta(z)}=[n^{-z}F(z)]=varphi(n))
因而得出 (varphi(n)=sumlimits_{d|n}dmu(n/d)cdotscdots(1.2.6))
但在 (F(z)=dfrac{zeta(z-1)}{zeta(z)}) 中把 (zeta(z)) 乘到左边得到 (F(z)zeta(z)=zeta(z-1))。
卷积后取两边系数得出 (sumlimits_{d|n}varphi(d)=ncdotscdots(1.2.7))
这其实是 ((1.2.6)) 莫反后能得到的结果。
还有一种玩法，在 (F(z)=dfrac{zeta(z-1)}{zeta(z)}) 中将 (zeta(z-1)) 除到左边得到 (F(z)dfrac{1}{zeta(z-1)}=dfrac{1}{zeta(z)})
那由 ((1.1.2)) 得出 (dfrac{1}{zeta(z-1)}) 是 (nmu(n)) 的 ( ext{dgf})
所以 (sumlimits_{d|n}dmu(d)varphi(n/d)=mu(n)cdotscdots(1.2.8))
(4.) (f(n)=mu(n)^2)
由于 (mu(n)) 是积性函数，所以 (mu(n)^2) 仍是积性函数。
而 (mu(p^k)^2=egin{cases}1,k=0\1,k=1\0,kgeq 2end{cases})
所以 (F(z)=prodlimits_{pin ext{Prime}}1+dfrac{1}{p^z}=prodlimits_{pin ext{Prime}}dfrac{1-p^{-2z}}{1-p^{-z}}=dfrac{zeta(z)}{zeta(2z)}cdotscdots(1.2.9))
这似乎并不与之前讨论的函数有多少密切的联系，因为 (zeta(2z)) 并不十分好处理，但将与接下来的几个函数产生一些有趣的结论。
(5.) (f(n)=lambda(n))
其中 (lambda(n)=(-1)^{Omega(n)}) ，(Omega(n)) 指 (n) 的质因子个数，相同的算多个。
若 (n=p_1^{alpha_1}p_2^{alpha_2}dots p_k^{alpha_k}) ，则 (Omega(n)=alpha_1+alpha_2+dots+alpha_k,lambda(n)=(-1)^{alpha_1+alpha_2+dots+alpha_k})
由于 (forall ij=n,Omega(i)+Omega(j)=Omega(n)) ，所以 (lambda(n)) 是完全积性的。
而 (lambda(p^k)=(-1)^k)
所以 (F(z)=prodlimits_{pin ext{Prime}}sumlimits_{kgeq 0}dfrac{(-1)^k}{p^{kz}}=prodlimits_{pin ext{Prime}}sumlimits_{kgeq 0}left(-p^{-z} ight)^k=prodlimits_{pin ext{Prime}}dfrac{1}{1+p^{-z}}=prodlimits_{pin ext{Prime}}dfrac{1-p^{-z}}{1-p^{2z}}=dfrac{zeta(2z)}{zeta(z)})
这竟然与 (mu(n)^2) 的 ( ext{dgf}) 完全是倒数关系！
所以 (sumlimits_{d|n}lambda(d)mu(n/d)^2=[n=1]cdotscdots(1.2.11))
(6.) (f(n)=[n ext{是完全平方数}])
这也显然是完全积性函数，(f(p^k)=[2|k])
所以 (F(z)=prodlimits_{pin ext{Prime}}sumlimits_{kgeq 0}dfrac{1}{p^{2kz}}=prodlimits_{pin ext{Prime}}dfrac{1}{1-p^{-2z}}=zeta(2z))
(zeta(2z)) 总算能找出了其每项系数。
与 ((1.2.9)) 相乘得到的卷积式是 (sumlimits_{d|n}[d ext{是完全平方数}]mu(n/d)^2=sumlimits_{d^2|n}muleft(dfrac{n}{d^2} ight)^2=1cdotscdots(1.2.12))
看起来比较奇怪，几个非负整数之和仅是 (1) ？其实确实如此。
若 (n=p_1^{alpha_1}p_2^{alpha_2}dots p_k^{alpha_k},eta_i=leftlfloordfrac{alpha_i}{2} ight floor) 则 (dleq p_1^{eta_1}p_2^{eta_2}dots p_k^{eta_k}) 且在取等时 (muleft(dfrac{n}{d^2} ight)^2=1) 。
但是但凡一个质数的指数少了 (1) ，(alpha_i-2(eta_i-1)geq 2) ，会出现平方因子，(mu) 值变为 (0) 。
再看看与 ((1.2.10)) 结合会出现什么：
由于 (dfrac{zeta(2z)}{zeta(z)} imes zeta(z)=zeta(2z))
取 (n^{-z}) 的系数得出 (sumlimits_{d|n}lambda(d)=[n ext{是完全平方数}]cdotscdots(1.2.13))
或者看作 (zeta(2z) imes dfrac{1}{zeta(z)}=dfrac{zeta(2z)}{zeta(z)})
那就得出 (sumlimits_{d|n}[d ext{是完全平方数}]mu(n/d)=sumlimits_{d^2|n}muleft(dfrac{n}{d^2} ight)=lambda(n)cdotscdots(1.2.14))
(7.) (f(n)=hatphi(n))
这是我乱搞的一个函数，近似于 (varphi) ，定义为 (hatphi(n)=nsumlimits_{p|n,pin ext{Prime}}1+dfrac{1}{p})
这显然还是积性函数，且 (hatphi(p^k)=egin{cases}1,k=0\left(1+dfrac{1}{p} ight)p^k,kgeq 1end{cases})
所以
这可以与很多 ( ext{dgf}) 乘起来有简洁的形式。
比如与 (lambda) 的 ( ext{dgf} dfrac{zeta(2z)}{zeta(z)}) 相乘得到 (zeta(z-1))
卷积写出来就是 (sumlimits_{d|n}hatphi(d)lambda(n/d)=ncdotscdots(1.2.16))
或者与 ([n ext{是完全平方数}]) 的 ( ext{dgf} zeta(2z)) 相乘得到 (zeta(z-1)zeta(z))
而 ([n^{-z}]zeta(z-1)zeta(z)=sumlimits_{d|n}d=sigma_1(n))
所以 (sumlimits_{d|n}[d ext{是完全平方数}]hatphi(n/d)=sumlimits_{d^2|n}hatphileft(dfrac{n}{d^2} ight)=sigma_1(n)cdotscdots(1.2.17))
其中 (sigma_k(n)) 定义为 (sigma_k(n)=sumlimits_{d|n}d^k)
(2.) 杜教筛
杜教筛是一种比较基本的筛法，配合 ( ext{dgf}) 较灵活，但时间复杂度上具有一定局限性。
假设要求 (S(n)=sumlimits_{k=1}^{n}f(k))
其主要思想是构造函数 (g) 与 (h) 使 (sumlimits_{d|k}g(d)f(k/d)=h(k)) ，即 (f) 与 (g) 的狄利克雷卷积为 (h) ，其中 (g) 与 (h) 的前缀和需能较快求出。
将卷积式两边关于 (k) 求和：
单独将 (d=1) 的项拎出来，有数论函数下 (g(1)=1) ，再将后面的求和放到等号另一边，就有：
(S(n)=sumlimits_{k=1}^{n}h(k)-sumlimits_{d=2}^{n}g(d)S(leftlfloordfrac{n}{d} ight floor)cdotscdots(1.3.1))
对于后面的式子可以数论分块递归下去求出。
先是 (h(k)) 要方便求前缀和，其次这里的数论分块中还需求出 (g(d)) 的前缀和。
对于每个搜到的 (S(m)) 要记录一下答案以免重复算，以保证时间复杂度。
关于时间复杂度的证明（参考了 ( ext{cmd}) 的博客 ）：
假定能在 (O(1)) 的时间内求出 (g,h) 的前缀和。
每次求 (S) 中传入的值一定能写成 (leftlfloordfrac{n}{k} ight floor) 的形式。
这是因为假设当前求 (S) 传入的值是 (m) ，每次数论分块时传下去的就会是 (leftlfloordfrac{m}{l} ight floor)。
但最初 (m=n) 且有 (leftlfloordfrac{leftlfloordfrac{n}{a} ight floor}{b} ight floor=leftlfloordfrac{n}{ab} ight floor) 所以求 (S) 中传入的值必然是 (leftlfloordfrac{n}{k} ight floor)。
由于 (leftlfloordfrac{n}{k} ight floor) 有 (O(sqrt n)) 个不同的值，不妨设为 (dfrac{n}{i},1leq ileq sqrt n)
而求 (S) 传入的值是 (m) 时就会花费 (O(sqrt m)) 的时间整除分块处理 ((1.3.2)) 中第二个求和符号。
那这样就能得出其时间复杂度为 (O(sumlimits_{i=1}^{sqrt n}sqrt {frac{n}{i}})=O(sqrt nint_{1}^{sqrt n}i^{-frac{1}{2}}di)=O(2sqrt nsqrt {sqrt n})=O(n^{frac{3}{4}}))
但如果能线性筛出 (T) 之内的 (S) ，那只需对 (n/igeq T) 的进行数论分块，可得出 (ileq n/T)
这样时间复杂度为：
(O(T+sumlimits_{i=1}^{n/T}sqrt {n/i})=O(T+2sqrt nsqrt {n/T})=O(T+n/sqrt T+n/sqrt T)geq O(3sqrt[3]{n^2})=O(n^{frac{2}{3}}))
当 (T=n^{frac{2}{3}}) 时取等，有最优时间复杂度 (O(n^{frac{2}{3}}))。
事实上 (g,h) 的前缀和并不一定必须要在 (O(1)) 的时间复杂度内求出。
由于对 (m) 数论分块时所需要的前缀和 (l-1,r) 都能写成 (leftlfloordfrac{m}{w} ight floor) 的形式。
而 (exists t,m=leftlfloordfrac{n}{t} ight floor)，所以 (g,h) 所需的前缀和也仅是 (leftlfloordfrac{n}{k} ight floor)
于是能发现 (g,h) 所需的前缀和之值与杜教筛能筛出来的完全相同。
也就是说，如果 (f*g=h) ，且 (g,h) 的前缀和都能在较快的时间内求出 (leftlfloordfrac{n}{k} ight floor) 的全部前缀和，那 (f) 就能在额外 (O(n^{frac{2}{3}})) 的时间内用杜教筛合并筛出。
但如果能求出 (f,g) 的全部 (leftlfloordfrac{n}{k} ight floor) 的前缀和，也能求出 (h) 的前缀和。
(sumlimits_{k=1}^{n}h(k)=sumlimits_{k=1}^{n}sumlimits_{d|k}f(d)g(n/d)=sumlimits_{d=1}^{n}f(d)sumlimits_{k=1}^{leftlfloor frac{n}{d} ight floor}g(k)cdotscdots(1.3.2))
这也能数论分块求出，需要的也仅是 (f,g) 在(leftlfloordfrac{n}{k} ight floor) 处的前缀和。
以 ( ext{cmd}) 的话总结，就是在 (f*g=h) 时能“知二筛一”。
先来一些简单的例子：
(1.) (mu(n))
由于 (mu(n)) 的 ( ext{dgf}) 是 (dfrac{1}{zeta(z)})
有 (sumlimits_{d|n}mu(d)=[n=1]) ，(g(n)=1,h(n)=[n=1]) ，这就是 ((1.2.3))。
所以 (g,h) 都能在 (O(1)) 的时间内求出，再杜教筛一下就能得出 (mu(n)) 的前缀和。
(2.) (varphi(n))
由于 (varphi(n)) 的 ( ext{dgf}) 是 (dfrac{zeta(z-1)}{zeta(z)})
有 (sumlimits_{d|n}varphi(n)=n) ，(g(n)=1,h(n)=n)，这式子就是 ((1.2.7))
因此 (g,h) 的前缀和还是能 (O(1)) 求出，再杜教筛出 (varphi(n)) 的前缀和。
这两题就是杜教筛模板
(3.) (nvarphi(n))
由 ((1.1.2)) 与上个例子知 (nvarphi(n)) 的 ( ext{dgf}) 是 (dfrac{zeta(z-2)}{zeta(z-1)})
所以 (sumlimits_{d|n}dvarphi(d)left(dfrac{n}{d} ight)=n^2)，(g(n)=n,h(n)=n^2)
仍能 (O(1)) 求出其前缀和。
但这个例子有一个很好的启示。
假设已有方法求出 (f(n)) 的前缀和，即构造出了 (sumlimits_{d|n}f(d)g(n/d)=h(n),F(z)G(z)=H(z))
那 (n^tf(n)) 的前缀和仍然能类似求出。
因为 (n^tf(n)) 的 ( ext{dgf}) 是 (F(z-t)) ，而上式能推出 (F(z-t)G(z-t)=H(z-t))
那只需构造 (g(n)leftarrow n^tg(n),h(n)leftarrow n^th(n)) 即可。
(4.) (lambda(n))
由 ((1.2.13)) 知 (sumlimits_{d|n}lambda(d)=[n ext{是完全平方数}])。
所以有 (g(n)=1 ,h(n)=[n ext{是完全平方数}])。
那在杜教筛时为了得知 (leftlfloordfrac{n}{k} ight floor) 处 (h) 的前缀和，可以将全部 (leftlfloorsqrt n ight floor) 个平方数找出来，对每个 (leftlfloordfrac{n}{k} ight floor) 的 (h) 前缀和一次 (operatorname{lowerbound}) 求出，就要花费 (O(sqrt nlog n)) 的时间，记得要把查过的记录下来，不然复杂度会退化。
那再配合杜教筛就能以 (O(n^{frac{2}{3}}+sqrt nlog n)) 的时间求出 (lambda) 的前缀和。
事实上在回过头去看 ((1.2.14)) 的式子 (sumlimits_{d^2|n}muleft(dfrac{n}{d^2} ight)=lambda(n))
所以 (sumlimits_{k=1}^{n}lambda(k)=sumlimits_{k=1}^{n}sumlimits_{d^2|k}muleft(dfrac{n}{d^2} ight)=sumlimits_{d=1}^{sqrt n}sumlimits_{d^2|k,1leq kleq n}muleft(dfrac{n}{d^2} ight)=sumlimits_{d=1}^{sqrt n}sumlimits_{k=1}^{leftlfloorfrac{n}{d^2} ight floor}mu(k))
这所需要的 (mu(n)) 的前缀和也属于 (leftlfloordfrac{n}{k} ight floor) ，那直接暴力统计 (d) 即可。
总时间复杂度为 (O(n^{frac{2}{3}}+sqrt n))
这其实也能反观 ( ext{dgf}) 的强大。
(5.) $mu(n)^2 $
按着之前的式子 ((1.2.11):) (sumlimits_{d|n}lambda(d)mu(n/d)^2=[n=1])
既然上文能 (O(n^{frac{2}{3}})) 求出 (lambda(n)) 在 (leftlfloordfrac{n}{k} ight floor) 处的前缀和。
所以能在额外 (O(n^{frac{2}{3}})) 的时间内求出 (mu(n)^2) 的前缀和。
但还有更优秀的时间复杂度：
既然 (mu(n)^2) 的 ( ext{dgf}) 是 (dfrac{zeta(z)}{zeta(2z)}=zeta(z) imes dfrac{1}{zeta(2z)})
而 (dfrac{1}{zeta(2z)}=prodlimits_{pin ext{Prime}}1-dfrac{1}{p^{2z}})
这可以看做一个 (f(p^k)egin{cases}1,k=0\-1,k=2\0, ext{otherwise}end{cases}) ，的积性函数函数 (f) 的 ( ext{dgf})。
所以 (mu ^2) 就是 (f) 与 (g(n)=1) 的卷积，能用 ((1.3.2)) 求出。
既然每个质数只在出现平方次时 (f) 有值，那这些 (p) 必定 (leq sqrt n)
所以有值的 (f) 必定是一些互不相同的质数之积的完全平方。
那仅需要找出 (m=p_1p_2dots p_kleq sqrt n) 的全部 (m) ，满足 (f(m^2)=(-1)^k=mu(m)) 。
(m) 的数的个数是比 (sqrt n) 略小一点。
所以时间复杂度因该比 (O(sqrt n)) 略小一点。
这可以轻松过掉 ( ext{P4318})
事实上这种方法也是基于后文将要讲述的 ( ext{PN}) 筛的一个特例。
(6.) (hatphi (n))
(hatphi(n)) 的 ( ext{dfg}) 是 (dfrac{zeta(z)zeta(z-1)}{zeta(2z)}) ，可以有很多方法求出。
由于 (dfrac{zeta(z)zeta(z-1)}{zeta(2z)} imesdfrac{zeta(2z)}{zeta(z)}=zeta(z-1))
所以 (sumlimits_{d|n}hatphi(n)lambda(n/d)=n,g(n)=lambda(n),h(n)=n)
其中 (lambda(n)) 可按之前所述的方法 (O(n^{frac{2}{3}})) 求出需要的值，那按 ((1.3.1)) 做就完了。
但 (dfrac{zeta(z)zeta(z-1)}{zeta(2z)} imeszeta(2z)=zeta(z)zeta(z-1))
所以 (sumlimits_{d|n}hatphi(d)[n/d ext{是完全平方数}]=sigma_1(n)) ，就是 ((1.2.17))
若取 (g(n)=[n ext{是完全平方数}],h(n)=sigma_1(n)) ， (g(n)) 的筛法之前已讲述，只需看 (sigma_1(m)) 的前缀和：
(sumlimits_{k=1}^{m}sigma_1(k)=sumlimits_{k=1}^msumlimits_{d|k}d=sumlimits_{d=1}^{m}dsumlimits_{d|k,1leq kleq m}1=sumlimits_{d=1}^{m}dleftlfloordfrac{n}{d} ight floor)
于是单次求 (m) 内的 (sigma_1(k)) 的前缀和就能以 (O(sqrt m)) 的时间。
而需要的 (m) 共有 (O(sqrt n)) 个 (leftlfloordfrac{n}{k} ight floor) ，总复杂度是 (O(sumlimits_{i=1}^{sqrt n}sqrt{n/i})=O(n^{frac{3}{4}})) ，这与上文杜教筛类似。
于是仍要筛出 (n^{frac{2}{3}}) 的所有 (sigma_1(k)) ，才有 (O(n^{frac{2}{3}})) 的时间复杂度。
还有一种方法： (dfrac{zeta(z)zeta(z-1)}{zeta(2z)}=dfrac{zeta(z)}{zeta(2z)} imes zeta(z-1))
于是能取 (f(n)=mu(n)^2,g(n)=n) ，就能按 ((3.1.2)) 筛出。
而 (mu(n)^2) 的前缀和按上文两种方法都有 (O(n^{frac{2}{3}})) 的方法求出需要的 (leftlfloordfrac{n}{k} ight floor) 处 的前缀和。（第二种方法的处理方式可参考上面 (sigma_1) 的求和）。
所以，在 ( ext{dgf}) 的帮助下轻而易举地得到了 (3) 种处理 (hatphi) 的前缀和的方法。
一些例题
( ext{P3768})
题意：求 (sumlimits_{i=1}^{n}sumlimits_{j=1}^{n}ijgcd (i,j),nleq 1.1 imes 10^9)
直接莫反推式子：
设 (S(m)=sumlimits_{i=1}^{m}sumlimits_{j=1}^{m}ij=dfrac{m^2(m+1)^2}{4},f(T)=T^2sumlimits_{k|T}mu(k))
那原式就是 (sumlimits_{T=1}^{n}f(T)g(leftlfloordfrac{n}{T} ight floor)) 可以直接数论分块算，但其中要 (f(T)) 的前缀和。
而数论分块的边界是 (leftlfloordfrac{n}{w} ight floor) 可以直接杜教筛出 (f(T)) 。
由上面 (1.) 与 (3.) 中的启示，直接构造 (g(n)=n^2,h(n)=1) 再杜教筛就没了。
( ext{P7504})
题意： 给出 (n,q) 求 (sumlimits_{x=1}^{n}[xot q]sumlimits_{i=1}^{x}[iot x]i,n,kleq 10^9) （原题就是求两次这个）
设 (r(k)=sumlimits_{i=1}^{k}[iot k]i) ，则原式只需要求 ([kot q]r(k)) 的前缀和。
对其莫反：
所以原式就是 (sumlimits_{k=1}^{n}[kot q]r(k)=dfrac{1}{2}left(1+sumlimits_{k=1}^{n}[kot q]kvarphi(k) ight))
那接下来就希望快速计算 ([kot q]kvarphi(k)) 的前缀和。
由于 ([kot q]Rightarrowforall i|k,[iot q] ext{且} [(k/i)ot q])
所以若 (h(n)=sumlimits_{d|n}f(d)g(n/d)) ，那就有 ([not q]h(n)=sumlimits_{d|n}[dot q]f(d)[(n/d)ot q]g(n/d))
那么在此例中有 (g(n)=n,h(n)=n^2) 即 (3.) 中所述。
为了杜教筛，接下来的问题就是 ([kot q]k) 的前缀和与 ([kot q]k^2) 的前缀和。
再将其莫反：
由于 (q) 的因子个数是 (O(log q)) 的，这个式子可以在搜到时直接 (O(log(p))) 算。
由于需要的在提前 (O(n^{frac{2}{3}})) 的线性筛后需要这么算的仅有 (O(n^{frac{1}{3}})) 。
所以这部分的总时间复杂度为 (O(n^{frac{1}{3}}log n))。
加上求 (p) 的所有因数以及杜教筛后总体时间复杂度为 (O(sqrt q+n^{frac{1}{3}}log n+n^{frac{2}{3}}))
( ext{U183339})
题意：
记 (r(t)=sumlimits_{k=1}^t kleft[gcd(k,t)=1
ight])
求 (sumlimits_{i=1}^n sumlimits_{j=1}^n (i^2+j^2+ij)r(gcd(i,j))mod 998244353,nleq 10^{10})
这也是道我乱搞的题，却无意间发现 (r(n)=dfrac{1}{2}left([n=1]+nvarphi(n) ight)) 竟然在上题中出现了。
那再莫反看看最终的那个式子要干啥：
这又能数论分块，先看看小括号后面的式子：
(sumlimits_{i=1}^{m}sumlimits_{j=1}^{m}i^2+j^2+ij=2sumlimits_{i=1}^{m}i^2+left(sumlimits_{i=1}^{m}i ight)^2=dfrac{m(m+1)(11m^2+7m)}{12})
而前面的为了求前缀和又需要杜教筛了。
由于 (T^2sumlimits_{d|T}r(d)mu(T/d)=dfrac{1}{2}left(T^2mu(T)+T^2sumlimits_{d|n}dvarphi(d)mu(T/d) ight))
其中 (T^2mu(T)) 的前缀和按上文某启发已很好求出，剩下的就是 (T^2sumlimits_{d|n}dvarphi(d)mu(T/d)) 的前缀和。
这玩意又是个卷积，除 (T^2) 外的 ( ext{dgf}) 是 (dfrac{zeta(z-2)}{zeta(z-1)} imesdfrac{1}{zeta(z)}=dfrac{zeta(z-2)}{zeta(z-1)zeta(z)})
所以 (T^2sumlimits_{d|T}r(d)mu(T/d)) 的 ( ext{dgf}) 就是 (dfrac{zeta(z-4)}{zeta(z-3)zeta(z-2)})
所以可以构造 (g(n)=[n^{-z}]zeta(z-3)zeta(z-2),h(n)=[n^{-z}]zeta(z-4)=n^4)
其中 (h(n)=n^4) 的前缀和很好求，是 (sumlimits_{i=1}^{m}i^4=dfrac{x(x+1)(2x+1)(3x^2+3x-1)}{30})
而 (g(n)=sumlimits_{d|n}d^3left(dfrac{n}{d} ight)^2=n^2sumlimits_{d|n}d)
所以 (sumlimits_{i=1}^{m}g(i)=sumlimits_{i=1}^{m}i^2sumlimits_{d|i}d=sumlimits_{d=1}^{m}d^2sumlimits_{i=1}^{leftlfloorfrac{n}{d} ight floor}i) ，可以数论分块 (sqrt m) 求出。
与之前所述一样，需预处理出前 (n^{frac{2}{3}}) 的前缀和，剩下的数论分块算，才能保证时间复杂度。
总时间复杂度为 (O(n^{frac{2}{3}}))
当然处理 (T^2sumlimits_{d|n}dvarphi(d)mu(T/d)) 的前缀和可以先求出 (d^3varphi(d)) 与 (d^2mu(d)) 的前缀和，再用 ((1.3.1)) 算。
但这样单是这里就要做 (3) 次杜教筛，上面的方法只用两次。
(3. ext{Powerful Number}) 筛
这本质上杜教筛的一个优化，在一些杜教筛难以单独解决时能很好化解。
假设要求 (sumlimits_{i=1}^{n}f(i)) ，其基本原理就是构造 (f=h imes g) ，则有：
(sumlimits_{k=1}^{n}f(k)=sumlimits_{k=1}^{n}sumlimits_{d|k}h(d)g(n/d)=sumlimits_{d=1}^{n}h(d)sumlimits_{k=1}^{leftlfloor frac{n}{d} ight floor}g(k)) 也就是 ((1.3.2))
但如果 (f) 能满足 (h(p)=0) ,就能有一个很妙的事情。
那就是若 (n=p_1^{alpha_1}p_2^{alpha_2}dots p_k^{alpha_k}) ，(h(n)) 仅在 (mathop{forall}limits_{1leq ileq k}alpha_igeq 2) 时有值。
这些 (n) 被称为 ( ext{Powerful Number}) ，简称 ( ext{PN}) ，它 (leq N) 的个数仅有 (O(sqrt N))
这是因为所有 ( ext{PN}) 都能写成 (a^2b^3) 的形式。
这只需将出现奇数次的质数 (p_i^{alpha_i},2|alpha_i) 取 (p_i^3) 并到 (b) 中，那剩余的就是平方数并到 (a) 中即可。
那 ( ext{PN}) 的个数就是：
那再看一下 (g(p)) 的值：(f(p)=h(1)g(p)+h(p)g(1)=g(p)) 。
所以现实中一般是构造 (g(p)=f(p)) ，然后根据 (f=g imes h) 就能反推出 (h)：
(f(p^k)=sumlimits_{i=0}^{k}g(p^{i})h(p^{k-i})Rightarrow h(p^k)=f(p^k)-sumlimits_{i=1}^{k}g(p^i)h(p^{k-i}))
那对每个 (leq sqrt n) 质数暴力枚举次数，再按上式处理就能得出 (h(p^k)) 的全部值。
而 (kleq log n,pi(n)=Oleft(dfrac{n}{log n} ight)) ，所以时间复杂度为 (Oleft(dfrac{sqrt n}{log n} imes log^2 n ight)=O(sqrt nlog n))，为了存下 (h(p^k)) 的空间复杂度就是 (O(sqrt n))
当然能求出 (h(p^k)) 的封闭形式，而不要递推，时间复杂度将是 (O(sqrt n))
那暴力搜出所有 ( ext{PN}) ，再按 (sumlimits_{k=1}^{n}f(k)=sumlimits_{d=1}^{n}h(d)sumlimits_{k=1}^{leftlfloor frac{n}{d} ight floor}g(k)) 求出来。
接下来要求的就是 (g) 的前缀和，在能杜教筛的时候，由于 (leftlfloordfrac{n}{d} ight floor) 一定是能在杜教筛中被处理出来，所以可以在这里再配合杜教筛求出，时间复杂度将是 (n^{frac{2}{3}}) 。
若 (g) 的前缀和能 (O(1)) 求出，时间就可以缩短为 (O(sqrt n)) 或 (O(sqrt nlog n)) ，取决于 (h(p^k)) 是否需要递推。
( ext{P5325})
题意：给定积性函数 (f(p^k)=p^k(p^k-1)) ，求 (sumlimits_{k=1}^{n}f(k),nleq 10^{10})
由于 (f(p)=p(p-1)) 考虑构造 (g(n)=nvarphi(n)) 。
那由 (h(p^k)=f(p^k)-sumlimits_{i=1}^{k}g(p^i)h(p^{k-i})) 就能推出 (h) 剩下的就是求 (g(n)=nvarphi(n)) 的前缀和，这是易得的。
于是就能 (O(n^{frac{2}{3}})) 解决。
loj #6053. 简单的函数
题意：给定积性函数 (f(p^k)=p operatorname{xor} k) ，求 (sumlimits_{k=1}^{n}f(k),nleq 10^{10})
由于当 (p eq 2) 时 (f(p)=p-1=varphi(p)) ，而当 (p=2) 时 (f(p)=3(p-1)=3varphi(p))
由于 (f) 是积性函数，那就可以构造 (g(n)=egin{cases}3varphi(n),2|n\varphi(n), ext{otherwise}end{cases})
那 (h) 仍容易以 (h(p^k)=f(p^k)-sumlimits_{i=1}^{k}g(p^i)h(p^{k-i})) 递推。
剩下要求的就是 (g) 的前缀和。
而 (g(n)=varphi(n)+[2|n]2varphi(n))，记 (S(n)=sumlimits_{k=1}^{n}varphi(k),S1(n)=sumlimits_{k=1}^{n}[2|k]varphi(k)) 。
那 (sumlimits_{k=1}^{n}g(k)=S(n)+S1(n))
其中 (S(n)) 是杜教筛容易求的，关键是 (S1(n)) ：
其中用到了 (varphi(ij)=dfrac{varphi(i)varphi(j)gcd(i,j)}{varphi(gcd(i,j))}) ，这能以 (varphi) 的式子轻松证明出来。
所以对每个 (S1(m)) 就能 (O(log n)) 求出。
这是因为需要的 (m=leftlfloordfrac{n}{k} ight floor) ，递推下去每次需要的 (leftlfloordfrac{m}{2} ight floor=leftlfloordfrac{leftlfloordfrac{n}{k} ight floor}{2} ight floor=leftlfloordfrac{n}{2k} ight floor) 是杜教筛 (S) 时必然会处理的。
而按照预处理前 (n^{frac{2}{3}}) 个 (S1) 后要算 (O(n^{frac{1}{3}})) 个 (S1(m)) ，时间为 (O(n^{frac{1}{3}}log n))
加上 ( ext{PN}) 筛及杜教筛的时间复杂度，总时间为 (O(sqrt nlog n+sqrt[3] nlog n+n^{frac{2}{3}}))
loj #6682. 梦中的数论
题意：求 (sumlimits_{i=1}^{n}sumlimits_{j=1}^{n}sumlimits_{k=1}^{n}[j|i][(j+k)|i],nleq 10^{10})
设 (f(i)=sumlimits_{j=1}^{i}sumlimits_{k=1}^{i}[j|i][(j+k)|i]) ，则原式为 (f(i)) 的前缀和。
而 ([j|i][(j+k)|i]) 相当于从 (i) 的因数中选出两个的方案数，为 (dbinom{sigma_0(i)}{2})
所以 (f(i)=dbinom{sigma_0(i)}{2}=dfrac{sigma_o(i)^2-sigma_0(i)}{2})
其中 (sigma_0(i)) 的前缀和是易得的：(sumlimits_{i=1}^{n}sumlimits_{d|i}=sumlimits_{d=1}^{n}leftlfloordfrac{n}{d} ight floor) 一次数论分块即可。
重点看 (sigma_0(i)^2) 的前缀和，这个积性函数不得不重推 ( ext{dgf}) 来探究。
为了下文表述方便，设 (f_p(x)=sumlimits_{kgeq 0}sigma(p^k)^2x^k) ，即设对每个质数 (p) 设 (x=p^{-z}) 转为贝尔级数的形式。
那 (sigma_0(i)^2) 的 ( ext{dgf}) 就是 (prodlimits_{pin ext{Prime}}f_p(p^{-z}))
由于 (sigma_0(p^k)^2=(k+1)^2)
所以 (f_p(x)=sumlimits_{kgeq 0}(k+1)^2x^k=sumlimits_{kgeq 0}k^2x^k+sumlimits_{kgeq 0}kx^k+dfrac{1}{1-x})
由于 (sumlimits_{kgeq 0}a_kx^k=F(x)Rightarrowsumlimits_{kgeq 0}t(k)a_kx^k=t(xmathrm{D})F(x)) ，其中 (xmathrm D) 代表对原式求导后乘 (x) 的算子，(t) 是一个多项式。
这用第二类 ( ext{Stirling Numbers}) 把 (t(k)) 每一项转为下降幂，再用具体数学的习题 ((6.13)) 容易证明。
所以
这式子十分简洁，于是 (sigma_0(i)^2) 的 ( ext{dgf}) 就是：
这可以看做 (zeta(z)^4 imes dfrac{1}{zeta(2z)}) ，而 (zeta(2z)=prodlimits_{pin ext{Prime}}1-p^{-2z}) 仅在分解后各个质数次幂为 (2) 的数中有值。
所以 (dfrac{1}{zeta(2z)}) 仅在 ( ext{PN}) 中的一部分中有值，个数小于 (sqrt n) ，能直接搜出来。
剩下的就是求 (zeta(z)^4) 的前缀和，可以杜教筛。
这相当于 (zeta(z)^2) 与自身的卷积，而为了求出 (zeta(z)^2) 需要 (zeta(z)) 与自身的卷积。
但 (zeta(z)^2) 与 (zeta(z)) 需要的仅是 (leftlfloordfrac{n}{k} ight floor) 处的 (O(sqrt n)) 个值，在预处理出前 (n^{frac{2}{3}}) 的前缀和后用杜教筛的时间复杂度是 (O(n^{frac{2}{3}}))
由于我比较懒，在处理前 (n^{frac{2}{3}}) 的 (zeta(z)^2,zeta(z)^4) 的前缀和时直接用了 ( ext{P5495}) 的方法多一个 (lnln n) 算。
那这样预处理的范围可以适当调整一下。
总时间复杂度是 (O(n^{frac{2}{3}}lnln n)) 或 (O(n^{frac{2}{3}})) ，取决于是否线性筛。
但即使是 (O(n^{frac{2}{3}}lnln n)) 的方法在 ( ext{loj}) 上也能跑的十分快，不可思议地快过了一部分 ( ext{Min25}) 筛。