狄利克雷生成函数与其应用

Y_B_X · 2021-10-10 00:00:54 · 个人记录

狄利克雷生成函数是数论中的一项重要工具，与 \text{OI} 也是一个不可分割的存在，能将一些数论式子推向本质，且能很好地构造筛法。

注：以下讨论若无特殊说明 p 代表一个质数，\text{Prime} 代表全体质数集。

1. 狄利克雷生成函数初步

\text{Part 1} 定义与基本定理

一般的，我们如下定义一个数论函数 f 的狄利克雷生成函数，简称 \text{dgf}：

与其他生成函数一样，取系数得到一般项是其主要目的之一，可记作 f(n)=[n^{-z}]F(z)

而耳熟能详的狄利克雷卷积，同其他生成函数一样，是两个狄利克雷生成函数的积。

若设 G(z)=\sum\limits_{n\geq 1}\dfrac{g(n)}{n^z} 则 f 与 g 的卷积就是 F(z)\times G(z)=H(z)

同样设 H(z)=\sum\limits_{n\geq 1}\dfrac{h(n)}{n^z} ，则有 h(n)=\sum\limits_{d|n}f(d)g(n/d) 。 \cdots\cdots(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) 的 \text{dgf} 是 F(z) ，则 n^tf(n) 的 \text{dgf} 是 F(z-t) 。 \cdots\cdots(1.1.2)

因为 \sum\limits_{n\geq 1}\dfrac{n^tf(n)}{n^z}=\sum\limits_{n\geq 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)=\sum\limits_{n\geq 1}\dfrac{f(n)}{n^z}=\prod\limits_{p\in \text{Prime}}1+\frac{f(p)}{p^z}+\frac{f(p^2)}{p^{2z}}+\frac{f(p^3)}{p^{3z}}+\dots=\prod\limits_{p\in \text{Prime}}\sum\limits_{k\geq 0}\dfrac{f(p^k)}{p^{kz}}\cdots\cdots(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)=\sum\limits_{k\geq 0}f(p^k)x^k ，称之为贝尔级数，本质上就是是狄利克雷生成函数的衍生，二者相互依存。

\text{Part 2} 简单的运用

1. f(n)=1

如果将 f(n)=1 带入其狄利克雷生成函数，得到 F(z)=\sum\limits_{n\geq 1}\dfrac{1}{n^z}=\zeta(z)

这就是黎曼 \zeta 函数，它将在接下来的运用中发挥重要作用。

由于 f(n)=1 满足积性函数的定义，所以可用 (1.1.3) 改写：

2. f(n)=\mu(n)

由于 \mu(n) 为积性函数，所以可以直接用 (1.1.3) 展开。

所以只用看对每个 p^k ，\mu(p^k) 的值。

所以 F(z)=\prod\limits_{p\in\text{Prime}}\sum\limits_{k\geq 0}\dfrac{\mu(p^k)}{p^{kz}}=\prod\limits_{p\in\text{Prime}}1+\dfrac{-1}{p^z}=\prod\limits_{p\in\text{Prime}}1-p^{-z}=\dfrac{1}{\zeta(z)}\cdots\cdots(1.2.2)

如果把右侧的 \zeta(z) 乘到左边，得到 F(z)\zeta(z)=1 。

取两边 n^{-z} 的系数，那 F(z)\zeta(z) 就是两个 \text{dgf} 的卷积，而右边仅在 n=1 时值为 1 。

所以 \sum\limits_{d|n}\mu(d)\times1=\sum\limits_{d|n}\mu(d)=[n=1]\cdots\cdots(1.2.3)

有了莫比乌斯函数的 \text{dgf} ，我们将揭示莫比乌斯反演的本质。

莫反的原式如下 g(n)=\sum\limits_{d|n}f(d)\Leftrightarrow f(n)=\sum\limits_{d|n}g(d)\mu(n/d)\cdots\cdots(1.2.4)

事实上由于卷积， g(n)=\sum\limits_{d|n}f(d) 可看做 G(z)=F(z)\zeta(z) ，两边 n^{-z} 的系数。

那把右边 \zeta(z) 除到左边，得到 G(z)\dfrac{1}{\zeta(z)}=F(z)

而莫比乌斯函数的 \text{dgf} 就是 \dfrac{1}{\zeta(z)} ，所以 G(z)\dfrac{1}{\zeta(z)} 就是 g 与 \mu 的卷积。

再取两边 n^{-z} 的系数就能得到 \sum\limits_{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)=n\sum\limits_{p|n,p\in \text{Prime}}1-\dfrac{1}{p} ，所以 \varphi 仍是一个积性函数。

为了求其 \text{dgf} 我们依然想得知 \varphi(p^k) 的值：

所以

因为 \dfrac{\zeta(z-1)}{\zeta(z)}=\zeta(z-1)\dfrac{1}{\zeta(z)} 是两个 \text{dgf} 的卷积。

而由 (1.1.2) \zeta(z-1) 是 n 的 \text{dgf} ，\dfrac{1}{\zeta(z)} 是 \mu(n) 的 \text{dgf}

所以 [n^{-z}]\dfrac{\zeta(z-1)}{\zeta(z)}=\sum\limits_{d|n}d\mu(n/d)

而 [n^{-z}]\dfrac{\zeta(z-1)}{\zeta(z)}=[n^{-z}F(z)]=\varphi(n)

因而得出 \varphi(n)=\sum\limits_{d|n}d\mu(n/d)\cdots\cdots(1.2.6)

但在 F(z)=\dfrac{\zeta(z-1)}{\zeta(z)} 中把 \zeta(z) 乘到左边得到 F(z)\zeta(z)=\zeta(z-1)。

卷积后取两边系数得出 \sum\limits_{d|n}\varphi(d)=n\cdots\cdots(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)} 是 n\mu(n) 的 \text{dgf}

所以 \sum\limits_{d|n}d\mu(d)\varphi(n/d)=\mu(n)\cdots\cdots(1.2.8)

4. f(n)=\mu(n)^2

由于 \mu(n) 是积性函数，所以 \mu(n)^2 仍是积性函数。

而 \mu(p^k)^2=\begin{cases}1,k=0\\1,k=1\\0,k\geq 2\end{cases}

所以 F(z)=\prod\limits_{p\in\text{Prime}}1+\dfrac{1}{p^z}=\prod\limits_{p\in\text{Prime}}\dfrac{1-p^{-2z}}{1-p^{-z}}=\dfrac{\zeta(z)}{\zeta(2z)}\cdots\cdots(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)=\prod\limits_{p\in\text{Prime}}\sum\limits_{k\geq 0}\dfrac{(-1)^k}{p^{kz}}=\prod\limits_{p\in\text{Prime}}\sum\limits_{k\geq 0}\left(-p^{-z}\right)^k=\prod\limits_{p\in\text{Prime}}\dfrac{1}{1+p^{-z}}=\prod\limits_{p\in\text{Prime}}\dfrac{1-p^{-z}}{1-p^{2z}}=\dfrac{\zeta(2z)}{\zeta(z)}

这竟然与 \mu(n)^2 的 \text{dgf} 完全是倒数关系！

所以 \sum\limits_{d|n}\lambda(d)\mu(n/d)^2=[n=1]\cdots\cdots(1.2.11)

6. f(n)=[n\text{是完全平方数}]

这也显然是完全积性函数，f(p^k)=[2|k]

所以 F(z)=\prod\limits_{p\in\text{Prime}}\sum\limits_{k\geq 0}\dfrac{1}{p^{2kz}}=\prod\limits_{p\in\text{Prime}}\dfrac{1}{1-p^{-2z}}=\zeta(2z)

看起来比较奇怪，几个非负整数之和仅是 1 ？其实确实如此。

若 n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k},\beta_i=\left\lfloor\dfrac{\alpha_i}{2}\right\rfloor 则 d\leq p_1^{\beta_1}p_2^{\beta_2}\dots p_k^{\beta_k} 且在取等时 \mu\left(\dfrac{n}{d^2}\right)^2=1 。

但是但凡一个质数的指数少了 1 ，\alpha_i-2(\beta_i-1)\geq 2 ，会出现平方因子，\mu 值变为 0 。

再看看与 (1.2.10) 结合会出现什么：

由于 \dfrac{\zeta(2z)}{\zeta(z)}\times \zeta(z)=\zeta(2z)

取 n^{-z} 的系数得出 \sum\limits_{d|n}\lambda(d)=[n\text{是完全平方数}]\cdots\cdots(1.2.13)

或者看作 \zeta(2z)\times \dfrac{1}{\zeta(z)}=\dfrac{\zeta(2z)}{\zeta(z)}

那就得出 \sum\limits_{d|n}[d\text{是完全平方数}]\mu(n/d)=\sum\limits_{d^2|n}\mu\left(\dfrac{n}{d^2}\right)=\lambda(n)\cdots\cdots(1.2.14)

这是我乱搞的一个函数，近似于 \varphi ，定义为 \hat\phi(n)=n\sum\limits_{p|n,p\in\text{Prime}}1+\dfrac{1}{p}

这显然还是积性函数，且 \hat\phi(p^k)=\begin{cases}1,k=0\\\left(1+\dfrac{1}{p}\right)p^k,k\geq 1\end{cases}

所以

这可以与很多 \text{dgf} 乘起来有简洁的形式。

比如与 \lambda 的 \text{dgf}\ \dfrac{\zeta(2z)}{\zeta(z)} 相乘得到 \zeta(z-1)

卷积写出来就是 \sum\limits_{d|n}\hat\phi(d)\lambda(n/d)=n\cdots\cdots(1.2.16)

或者与 [n\text{是完全平方数}] 的 \text{dgf}\ \zeta(2z) 相乘得到 \zeta(z-1)\zeta(z)

而 [n^{-z}]\zeta(z-1)\zeta(z)=\sum\limits_{d|n}d=\sigma_1(n)

所以 \sum\limits_{d|n}[d\text{是完全平方数}]\hat\phi(n/d)=\sum\limits_{d^2|n}\hat\phi\left(\dfrac{n}{d^2}\right)=\sigma_1(n)\cdots\cdots(1.2.17)

其中 \sigma_k(n) 定义为 \sigma_k(n)=\sum\limits_{d|n}d^k

2. 杜教筛

杜教筛是一种比较基本的筛法，配合 \text{dgf} 较灵活，但时间复杂度上具有一定局限性。

假设要求 S(n)=\sum\limits_{k=1}^{n}f(k)

其主要思想是构造函数 g 与 h 使 \sum\limits_{d|k}g(d)f(k/d)=h(k) ，即 f 与 g 的狄利克雷卷积为 h ，其中 g 与 h 的前缀和需能较快求出。

将卷积式两边关于 k 求和：

单独将 d=1 的项拎出来，有数论函数下 g(1)=1 ，再将后面的求和放到等号另一边，就有：

对于后面的式子可以数论分块递归下去求出。

先是 h(k) 要方便求前缀和，其次这里的数论分块中还需求出 g(d) 的前缀和。

对于每个搜到的 S(m) 要记录一下答案以免重复算，以保证时间复杂度。

关于时间复杂度的证明（参考了 \text{cmd} 的博客 ）：

假定能在 O(1) 的时间内求出 g,h 的前缀和。

每次求 S 中传入的值一定能写成 \left\lfloor\dfrac{n}{k}\right\rfloor 的形式。

这是因为假设当前求 S 传入的值是 m ，每次数论分块时传下去的就会是 \left\lfloor\dfrac{m}{l}\right\rfloor。

但最初 m=n 且有 \left\lfloor\dfrac{\left\lfloor\dfrac{n}{a}\right\rfloor}{b}\right\rfloor=\left\lfloor\dfrac{n}{ab}\right\rfloor 所以求 S 中传入的值必然是 \left\lfloor\dfrac{n}{k}\right\rfloor。

由于 \left\lfloor\dfrac{n}{k}\right\rfloor 有 O(\sqrt n) 个不同的值，不妨设为 \dfrac{n}{i},1\leq i\leq \sqrt n

而求 S 传入的值是 m 时就会花费 O(\sqrt m) 的时间整除分块处理 (1.3.1) 中第二个求和符号。

那这样就能得出其时间复杂度为 O(\sum\limits_{i=1}^{\sqrt n}\sqrt {\frac{n}{i}})=O(\sqrt n\int_{1}^{\sqrt n}i^{-\frac{1}{2}}di)=O(2\sqrt n\sqrt {\sqrt n})=O(n^{\frac{3}{4}})

但如果能线性筛出 T 之内的 S ，那只需对 n/i\geq T 的进行数论分块，可得出 i\leq n/T

这样时间复杂度为：

当 T=n^{\frac{2}{3}} 时取等，有最优时间复杂度 O(n^{\frac{2}{3}})。

事实上 g,h 的前缀和并不一定必须要在 O(1) 的时间复杂度内求出。

由于对 m 数论分块时所需要的前缀和 l-1,r 都能写成 \left\lfloor\dfrac{m}{w}\right\rfloor 的形式。

而 \exists t,m=\left\lfloor\dfrac{n}{t}\right\rfloor，所以 g,h 所需的前缀和也仅是 \left\lfloor\dfrac{n}{k}\right\rfloor

于是能发现 g,h 所需的前缀和之值与杜教筛能筛出来的完全相同。

也就是说，如果 f*g=h ，且 g,h 的前缀和都能在较快的时间内求出 \left\lfloor\dfrac{n}{k}\right\rfloor 的全部前缀和，那 f 就能在额外 O(n^{\frac{2}{3}}) 的时间内用杜教筛合并筛出。

但如果能求出 f,g 的全部 \left\lfloor\dfrac{n}{k}\right\rfloor 的前缀和，也能求出 h 的前缀和。

这也能数论分块求出，需要的也仅是 f,g 在\left\lfloor\dfrac{n}{k}\right\rfloor 处的前缀和。

以 \text{cmd} 的话总结，就是在 f*g=h 时能“知二筛一”。

先来一些简单的例子：

1. \mu(n)

由于 \mu(n) 的 \text{dgf} 是 \dfrac{1}{\zeta(z)}

有 \sum\limits_{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) 的 \text{dgf} 是 \dfrac{\zeta(z-1)}{\zeta(z)}

有 \sum\limits_{d|n}\varphi(n)=n ，g(n)=1,h(n)=n，这式子就是 (1.2.7)

因此 g,h 的前缀和还是能 O(1) 求出，再杜教筛出 \varphi(n) 的前缀和。

这两题就是杜教筛模板

3. n\varphi(n)

由 (1.1.2) 与上个例子知 n\varphi(n) 的 \text{dgf} 是 \dfrac{\zeta(z-2)}{\zeta(z-1)}

所以 \sum\limits_{d|n}d\varphi(d)\left(\dfrac{n}{d}\right)=n^2，g(n)=n,h(n)=n^2

仍能 O(1) 求出其前缀和。

但这个例子有一个很好的启示。

假设已有方法求出 f(n) 的前缀和，即构造出了 \sum\limits_{d|n}f(d)g(n/d)=h(n),F(z)G(z)=H(z)

那 n^tf(n) 的前缀和仍然能类似求出。

因为 n^tf(n) 的 \text{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) 知 \sum\limits_{d|n}\lambda(d)=[n\text{是完全平方数}]。

所以有 g(n)=1 ,h(n)=[n\text{是完全平方数}]。

那在杜教筛时为了得知 \left\lfloor\dfrac{n}{k}\right\rfloor 处 h 的前缀和，可以将全部 \left\lfloor\sqrt n\right\rfloor 个平方数找出来，对每个 \left\lfloor\dfrac{n}{k}\right\rfloor 的 h 前缀和一次 \operatorname{lowerbound} 求出，就要花费 O(\sqrt n\log n) 的时间，记得要把查过的记录下来，不然复杂度会退化。

那再配合杜教筛就能以 O(n^{\frac{2}{3}}+\sqrt n\log n) 的时间求出 \lambda 的前缀和。

事实上在回过头去看 (1.2.14) 的式子 \sum\limits_{d^2|n}\mu\left(\dfrac{n}{d^2}\right)=\lambda(n)

所以 \sum\limits_{k=1}^{n}\lambda(k)=\sum\limits_{k=1}^{n}\sum\limits_{d^2|k}\mu\left(\dfrac{k}{d^2}\right)=\sum\limits_{d=1}^{\sqrt n}\sum\limits_{d^2|k,1\leq k\leq n}\mu\left(\dfrac{k}{d^2}\right)=\sum\limits_{d=1}^{\sqrt n}\sum\limits_{1\leq kd^2\leq n}\mu(k)=\sum\limits_{d=1}^{\sqrt n}\sum\limits_{k=1}^{\left\lfloor\frac{n}{d^2}\right\rfloor}\mu(k)

这所需要的 \mu(n) 的前缀和也属于 \left\lfloor\dfrac{n}{k}\right\rfloor ，那直接暴力统计 d 即可。

总时间复杂度为 O(n^{\frac{2}{3}}+\sqrt n)

这其实也能反观 \text{dgf} 的强大。

5. \mu(n)^2

按着之前的式子 (1.2.11): \sum\limits_{d|n}\lambda(d)\mu(n/d)^2=[n=1]

既然上文能 O(n^{\frac{2}{3}}) 求出 \lambda(n) 在 \left\lfloor\dfrac{n}{k}\right\rfloor 处的前缀和。

所以能在额外 O(n^{\frac{2}{3}}) 的时间内求出 \mu(n)^2 的前缀和。

但还有更优秀的时间复杂度：

既然 \mu(n)^2 的 \text{dgf} 是 \dfrac{\zeta(z)}{\zeta(2z)}=\zeta(z)\times \dfrac{1}{\zeta(2z)}

而 \dfrac{1}{\zeta(2z)}=\prod\limits_{p\in \text{Prime}}1-\dfrac{1}{p^{2z}}

这可以看做一个 f(p^k)=\begin{cases}1,k=0\\-1,k=2\\0,\text{otherwise}\end{cases} ，的积性函数函数 f 的 \text{dgf}。

所以 \mu ^2 就是 f 与 g(n)=1 的卷积，能用 (1.3.2) 求出。

既然每个质数只在出现平方次时 f 有值，那这些 p 必定 \leq \sqrt n

所以有值的 f 必定是一些互不相同的质数之积的完全平方。

那仅需要找出 m=p_1p_2\dots p_k\leq \sqrt n 的全部 m ，满足 f(m^2)=(-1)^k=\mu(m) 。

所以 \sum\limits_{d|n}\hat\phi(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)}\times\zeta(2z)=\zeta(z)\zeta(z-1)

所以 \sum\limits_{d|n}\hat\phi(d)[n/d\text{是完全平方数}]=\sigma_1(n) ，就是 (1.2.17)

若取 g(n)=[n\text{是完全平方数}],h(n)=\sigma_1(n) ， g(n) 的筛法之前已讲述，只需看 \sigma_1(m) 的前缀和：

于是单次求 m 内的 \sigma_1(k) 的前缀和就能以 O(\sqrt m) 的时间。

而需要的 m 共有 O(\sqrt n) 个 \left\lfloor\dfrac{n}{k}\right\rfloor ，总复杂度是 O(\sum\limits_{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)}\times \zeta(z-1)

于是能取 f(n)=\mu(n)^2,g(n)=n ，就能按 (3.1.2) 筛出。

而 \mu(n)^2 的前缀和按上文两种方法都有 O(n^{\frac{2}{3}}) 的方法求出需要的 \left\lfloor\dfrac{n}{k}\right\rfloor 处 的前缀和。（第二种方法的处理方式可参考上面 \sigma_1 的求和）。

所以，在 \text{dgf} 的帮助下轻而易举地得到了 3 种处理 \hat\phi 的前缀和的方法。

一些例题

\text{P3768}

题意：求 \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}ij\gcd (i,j),n\leq 1.1\times 10^9

直接莫反推式子：

设 S(m)=\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{m}ij=\dfrac{m^2(m+1)^2}{4},f(T)=T^2\sum\limits_{k|T}\mu(k)

那原式就是 \sum\limits_{T=1}^{n}f(T)g(\left\lfloor\dfrac{n}{T}\right\rfloor) 可以直接数论分块算，但其中要 f(T) 的前缀和。

而数论分块的边界是 \left\lfloor\dfrac{n}{w}\right\rfloor 可以直接杜教筛出 f(T) 。

由上面 1. 与 3. 中的启示，直接构造 g(n)=n^2,h(n)=1 再杜教筛就没了。

\text{P7504}

题意： 给出 n,q 求 \sum\limits_{x=1}^{n}[x\bot q]\sum\limits_{i=1}^{x}[i\bot x]i,n,k\leq 10^9 （原题就是求两次这个）

设 r(k)=\sum\limits_{i=1}^{k}[i\bot k]i ，则原式只需要求 [k\bot q]r(k) 的前缀和。

对其莫反：

所以原式就是 \sum\limits_{k=1}^{n}[k\bot q]r(k)=\dfrac{1}{2}\left(1+\sum\limits_{k=1}^{n}[k\bot q]k\varphi(k)\right)

那接下来就希望快速计算 [k\bot q]k\varphi(k) 的前缀和。

由于 [k\bot q]\Rightarrow\forall i|k,[i\bot q] \text{且} [(k/i)\bot q]

所以若 h(n)=\sum\limits_{d|n}f(d)g(n/d) ，那就有 [n\bot q]h(n)=\sum\limits_{d|n}[d\bot q]f(d)[(n/d)\bot q]g(n/d)

那么在此例中有 g(n)=n,h(n)=n^2 即 3. 中所述。

为了杜教筛，接下来的问题就是 [k\bot q]k 的前缀和与 [k\bot 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}})

\text{U183339}

题意：
记 r(t)=\sum\limits_{k=1}^t k\left[\gcd(k,t)=1\right]
求 \sum\limits_{i=1}^n \sum\limits_{j=1}^n (i^2+j^2+ij)r(\gcd(i,j))\bmod 998244353,n\leq 10^{10}

这也是道我乱搞的题，却无意间发现 r(n)=\dfrac{1}{2}\left([n=1]+n\varphi(n)\right) 竟然在上题中出现了。

那再莫反看看最终的那个式子要干啥：

这又能数论分块，先看看小括号后面的式子：

而前面的为了求前缀和又需要杜教筛了。

由于 T^2\sum\limits_{d|T}r(d)\mu(T/d)=\dfrac{1}{2}\left(T^2\mu(T)+T^2\sum\limits_{d|n}d\varphi(d)\mu(T/d)\right)

其中 T^2\mu(T) 的前缀和按上文某启发已很好求出，剩下的就是 T^2\sum\limits_{d|n}d\varphi(d)\mu(T/d) 的前缀和。

这玩意又是个卷积，除 T^2 外的 \text{dgf} 是 \dfrac{\zeta(z-2)}{\zeta(z-1)}\times\dfrac{1}{\zeta(z)}=\dfrac{\zeta(z-2)}{\zeta(z-1)\zeta(z)}

所以 T^2\sum\limits_{d|T}r(d)\mu(T/d) 的 \text{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 的前缀和很好求，是 \sum\limits_{i=1}^{m}i^4=\dfrac{x(x+1)(2x+1)(3x^2+3x-1)}{30}

而 g(n)=\sum\limits_{d|n}d^3\left(\dfrac{n}{d}\right)^2=n^2\sum\limits_{d|n}d

所以 \sum\limits_{i=1}^{m}g(i)=\sum\limits_{i=1}^{m}i^2\sum\limits_{d|i}d=\sum\limits_{d=1}^{m}d^2\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}i ，可以数论分块 \sqrt m 求出。

与之前所述一样，需预处理出前 n^{\frac{2}{3}} 的前缀和，剩下的数论分块算，才能保证时间复杂度。

总时间复杂度为 O(n^{\frac{2}{3}})

当然处理 T^2\sum\limits_{d|n}d\varphi(d)\mu(T/d) 的前缀和可以先求出 d^3\varphi(d) 与 d^2\mu(d) 的前缀和，再用 (1.3.1) 算。

但这样单是这里就要做 3 次杜教筛，上面的方法只用两次。

3.\text{Powerful Number} 筛

这本质上杜教筛的一个优化，在一些杜教筛难以单独解决时能很好化解。

假设要求 \sum\limits_{i=1}^{n}f(i) ，其基本原理就是构造 f=h\times g ，则有：

但如果 f 能满足 h(p)=0 ,就能有一个很妙的事情。

那就是若 n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k} ，h(n) 仅在 \mathop{\forall}\limits_{1\leq i\leq k}\alpha_i\geq 2 时有值。

这些 n 被称为 \text{Powerful Number} ，简称 \text{PN} ，它 \leq N 的个数仅有 O(\sqrt N)

这是因为所有 \text{PN} 都能写成 a^2b^3 的形式。

这只需将出现奇数次的质数 p_i^{\alpha_i},2|\alpha_i 取 p_i^3 并到 b 中，那剩余的就是平方数并到 a 中即可。

那 \text{PN} 的个数就是：

那再看一下 g(p) 的值：f(p)=h(1)g(p)+h(p)g(1)=g(p) 。

所以现实中一般是构造 g(p)=f(p) ，然后根据 f=g\times h 就能反推出 h：

那对每个 \leq \sqrt n 质数暴力枚举次数，再按上式处理就能得出 h(p^k) 的全部值。

而 k\leq \log n,\pi(n)=O\left(\dfrac{n}{\log n}\right) ，所以时间复杂度为 O\left(\dfrac{\sqrt n}{\log n}\times \log^2 n\right)=O(\sqrt n\log n)，为了存下 h(p^k) 的空间复杂度就是 O(\sqrt n)

当然能求出 h(p^k) 的封闭形式，而不要递推，时间复杂度将是 O(\sqrt n)

那暴力搜出所有 \text{PN} ，再按 \sum\limits_{k=1}^{n}f(k)=\sum\limits_{d=1}^{n}h(d)\sum\limits_{k=1}^{\left\lfloor \frac{n}{d}\right\rfloor}g(k) 求出来。

接下来要求的就是 g 的前缀和，在能杜教筛的时候，由于 \left\lfloor\dfrac{n}{d}\right\rfloor 一定是能在杜教筛中被处理出来，所以可以在这里再配合杜教筛求出，时间复杂度将是 n^{\frac{2}{3}} 。

若 g 的前缀和能 O(1) 求出，时间就可以缩短为 O(\sqrt n) 或 O(\sqrt n\log n) ，取决于 h(p^k) 是否需要递推。

\text{P5325}

题意：给定积性函数 f(p^k)=p^k(p^k-1) ，求 \sum\limits_{k=1}^{n}f(k),n\leq 10^{10}

由于 f(p)=p(p-1) 考虑构造 g(n)=n\varphi(n) 。

那由 h(p^k)=f(p^k)-\sum\limits_{i=1}^{k}g(p^i)h(p^{k-i}) 就能推出 h 剩下的就是求 g(n)=n\varphi(n) 的前缀和，这是易得的。

于是就能 O(n^{\frac{2}{3}}) 解决。

loj #6053. 简单的函数

题意：给定积性函数 f(p^k)=p \operatorname{xor} k ，求 \sum\limits_{k=1}^{n}f(k),n\leq 10^{10}

由于当 p\neq 2 时 f(p)=p-1=\varphi(p) ，而当 p=2 时 f(p)=3(p-1)=3\varphi(p)

由于 f 是积性函数，那就可以构造 g(n)=\begin{cases}3\varphi(n),2|n\\\varphi(n),\text{otherwise}\end{cases}

那 h 仍容易以 h(p^k)=f(p^k)-\sum\limits_{i=1}^{k}g(p^i)h(p^{k-i}) 递推。

剩下要求的就是 g 的前缀和。

而 g(n)=\varphi(n)+[2|n]2\varphi(n)，记 S(n)=\sum\limits_{k=1}^{n}\varphi(k),S1(n)=\sum\limits_{k=1}^{n}[2|k]\varphi(k) 。

那 \sum\limits_{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=\left\lfloor\dfrac{n}{k}\right\rfloor ，递推下去每次需要的 \left\lfloor\dfrac{m}{2}\right\rfloor=\left\lfloor\dfrac{\left\lfloor\dfrac{n}{k}\right\rfloor}{2}\right\rfloor=\left\lfloor\dfrac{n}{2k}\right\rfloor 是杜教筛 S 时必然会处理的。

而按照预处理前 n^{\frac{2}{3}} 个 S1 后要算 O(n^{\frac{1}{3}}) 个 S1(m) ，时间为 O(n^{\frac{1}{3}}\log n)

加上 \text{PN} 筛及杜教筛的时间复杂度，总时间为 O(\sqrt n\log n+\sqrt[3] n\log n+n^{\frac{2}{3}})

loj #6682. 梦中的数论

题意：求 \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{k=1}^{n}[j|i][(j+k)|i],n\leq 10^{10}

设 f(i)=\sum\limits_{j=1}^{i}\sum\limits_{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) 的前缀和是易得的：\sum\limits_{i=1}^{n}\sum\limits_{d|i}=\sum\limits_{d=1}^{n}\left\lfloor\dfrac{n}{d}\right\rfloor 一次数论分块即可。

重点看 \sigma_0(i)^2 的前缀和，这个积性函数不得不重推 \text{dgf} 来探究。

为了下文表述方便，设 f_p(x)=\sum\limits_{k\geq 0}\sigma(p^k)^2x^k ，即设对每个质数 p 设 x=p^{-z} 转为贝尔级数的形式。

那 \sigma_0(i)^2 的 \text{dgf} 就是 \prod\limits_{p\in \text{Prime}}f_p(p^{-z})

由于 \sigma_0(p^k)^2=(k+1)^2

所以 f_p(x)=\sum\limits_{k\geq 0}(k+1)^2x^k=\sum\limits_{k\geq 0}k^2x^k+\sum\limits_{k\geq 0}kx^k+\dfrac{1}{1-x}

由于 \sum\limits_{k\geq 0}a_kx^k=F(x)\Rightarrow\sum\limits_{k\geq 0}t(k)a_kx^k=t(x\mathrm{D})F(x) ，其中 x\mathrm D 代表对原式求导后乘 x 的算子，t 是一个多项式。

这用第二类 \text{Stirling Numbers} 把 t(k) 每一项转为下降幂，再用具体数学的习题 (6.13) 容易证明。

所以

这式子十分简洁，于是 \sigma_0(i)^2 的 \text{dgf} 就是：

这可以看做 \zeta(z)^4\times \dfrac{1}{\zeta(2z)} ，而 \zeta(2z)=\prod\limits_{p\in \text{Prime}}1-p^{-2z} 仅在分解后各个质数次幂为 2 的数中有值。

所以 \dfrac{1}{\zeta(2z)} 仅在 \text{PN} 中的一部分中有值，个数小于 \sqrt n ，能直接搜出来。

剩下的就是求 \zeta(z)^4 的前缀和，可以杜教筛。

这相当于 \zeta(z)^2 与自身的卷积，而为了求出 \zeta(z)^2 需要 \zeta(z) 与自身的卷积。

但 \zeta(z)^2 与 \zeta(z) 需要的仅是 \left\lfloor\dfrac{n}{k}\right\rfloor 处的 O(\sqrt n) 个值，在预处理出前 n^{\frac{2}{3}} 的前缀和后用杜教筛的时间复杂度是 O(n^{\frac{2}{3}})

由于我比较懒，在处理前 n^{\frac{2}{3}} 的 \zeta(z)^2,\zeta(z)^4 的前缀和时直接用了 \text{P5495} 的方法多一个 \ln\ln n 算。

那这样预处理的范围可以适当调整一下。

总时间复杂度是 O(n^{\frac{2}{3}}\ln\ln n) 或 O(n^{\frac{2}{3}}) ，取决于是否线性筛。

但即使是 O(n^{\frac{2}{3}}\ln\ln n) 的方法在 \text{loj} 上也能跑的十分快，不可思议地快过了一部分 \text{Min25} 筛。