狄利克雷生成函数

狄利克雷卷积

定义两个数论函数 $f,g$ 的狄利克雷卷积 $f\ast g$ 为：

$$(f\ast g)(n)=\sum_{d\mid n} f(d)g\left(\frac{n}{d}\right)$$

狄利克雷卷积有以下（容易证明的）基本性质：

• 交换律 $f\ast g=g\ast f$。
• 结合律 $f\ast (g\ast h)=(f\ast g)\ast h$。
• 分配律 $f\ast (g+h)=f\ast g+f\ast h$。

几个常见的数论函数可以用狄利克雷卷积连接：$\mu\ast 1=\epsilon,\varphi\ast 1=\mathrm{id},\mu\ast \mathrm{id}=\varphi$。

狄利克雷卷积的单位元为指示函数 $\epsilon(n)=[n=1]$。

狄利克雷生成函数

狄利克雷生成函数是研究积性函数的好工具。

对于数论函数 $f(n)$，定义其的狄利克雷生成函数为：

$$\mathbf{F}(z)=\sum_{i\geq 1} f(i)i^{-z}$$

根据狄利克雷生成函数的定义，可以写出 Wolfram 代码：

DirichletGF[f_, z_] := Sum[f[n] n^(-z), {n, 1, Infinity}]

为了方便，下面我们用加粗的大写字母来表示一个函数的狄利克雷生成函数。

狄利克雷生成函数有一个重要性质：

定理：对于积性函数 $f(n)$ 及其狄利克雷生成函数 $\mathbf{F}(z)$，有：

$$\mathbf{F}(z)=\prod_{p\in\mathbb{P}} \sum_{i\geq 0} f(p^i)p^{-iz}$$

证明是容易的，根据算术基本定理以及积性函数的定义，取每个数的质因数分解即可得到。

狄利克雷生成函数的卷积，对应数论函数的狄利克雷卷积：

$$\mathbf{F}(z)\cdot \mathbf{G}(z)=\sum_{i\geq 1} \sum_{j\geq 1} f(i)g(j)(ij)^{-z}=\sum_{d\geq 1}d^{-z}\sum_{i\mid d} f(i)g\left(\frac{d}{i}\right)=\sum_{d\geq 1} (f\ast g)(z)\cdot d^{-z}$$

常见数论函数的生成函数

指示函数 $\epsilon(n)=[n=1]$。它的狄利克雷生成函数为：

$$\mathbf{E}(z)=\sum_{i\geq 1} \epsilon(i)i^{-z} = 1^{-z} = 1$$

常数函数 $1(n)=1$（为了防止歧义，下面用 $c(n)$ 代指常数函数）。它的狄利克雷生成函数为：

$$\mathbf{C}(z)=\sum_{i\geq 1} i^{-z}=\zeta(z)$$

其中 $\zeta(z)$ 就是著名的黎曼 zeta 函数。

幂函数 $\mathrm{id}_k(z)=z^k$，它的狄利克雷生成函数为：

$$\mathbf{ID}_k(z)=\sum_{i\geq 1} i^k\cdot i^{-z}=\sum_{i\geq 1} i^{-(z-k)}=\zeta(z-k)$$

幂函数的重要特例是恒等函数 $\mathrm{id}(z)=z$，它的狄利克雷生成函数为 $\zeta(z-1)$。

根据基本性质 $\mu\ast 1=\epsilon$，易得莫比乌斯函数 $\mu(n)$ 的狄利克雷生成函数为：

$$\mathbf{M}(z)=\frac{\mathbf{E}(z)}{\mathbf{C}(z)}=\frac{1}{\zeta(z)}$$

根据基本性质 $\mu\ast \mathrm{id}=\varphi$，易得欧拉函数 $\varphi(n)$ 的狄利克雷生成函数为：

$$\mathbf{\Phi}(z)=\mathbf{M}(z)\cdot \mathbf{ID}(z)=\frac{\zeta(z-1)}{\zeta(z)}$$

根据除数函数的定义 $\mathrm{id}_k\ast 1=\sigma_k$，易得除数函数 $\sigma_k(n)$ 的狄利克雷生成函数为：

$$\mathbf{\Sigma}_k(z)=\mathbf{ID}_k(z)\cdot \mathbf{C}(z)=\zeta(z)\zeta(z-k)$$

除数函数的特例是约数个数函数 $d(n)=\sigma_1(n)$，它的狄利克雷生成函数为 $\zeta(z)\zeta(z-1)$。

整理：

函数	中文名	狄利克雷生成函数
$\epsilon$	指示函数	$\mathbf{E}(z)=1$
$1$	常数函数	$\mathbf{C}(z)=\zeta(z)$
$\mathrm{id}_k$	幂函数	$\mathbf{ID}_k(z)=\zeta(z-k)$
$\mathrm{id}$	恒等函数	$\mathbf{ID}(z)=\zeta(z-1)$
$\mu$	莫比乌斯函数	$\mathbf{M}(z)=\frac{1}{\zeta(z)}$
$\varphi$	欧拉函数	$\mathbf{\Phi}(z)=\frac{\zeta(z-1)}{\zeta(z)}$
$\sigma_k$	除数函数	$\mathbf{\Sigma}_k(z)=\zeta(z)\zeta(z-k)$
$d$	约数个数函数	$\mathbf{D}(z)=\zeta(z)\zeta(z-1)$

我们可以用 Wolfram 语言来检验这些结果：

DirichletGF[f_, z_] := Sum[f[n] n^(-z), {n, 1, Infinity}]
DirichletGF[If[# == 1, 1, 0] &, z] (* 指示函数，期望结果 1 *)
DirichletGF[1 &, z] (* 常数函数，期望结果 Zeta[z] *)
DirichletGF[#^k &, z] (* 幂函数，期望结果 Zeta[-k+z] *)
DirichletGF[MoebiusMu, z] (* 莫比乌斯函数，期望结果 1/Zeta[z] *)
DirichletGF[EulerPhi, z] (* 欧拉函数，期望结果 Zeta[-1+z]/Zeta[z] *)
DirichletGF[DivisorSigma[k, #] &, z] (* 除数函数，期望结果 Zeta[z] Zeta[-k+z] *)

高级筛法

求数论函数前缀和是一个经典的问题，用线性筛法可以做到 $O(n)$，不过这并不是终点，高级筛法一般用于在亚线性时间复杂度内求数论函数的前缀和。

常见的高级筛法有杜教筛、Min_25 筛、洲阁筛、Powerful Number 筛等等。

杜教筛

流程

杜教筛是最基本的高级筛法，它的时间复杂度较为优秀（$O(n^{2/3})$），但并不是所有数论函数都可以用杜教筛求和。

假设我们要求 $f(n)$ 的前缀和 $F(n)$，则需要构造两个函数 $g,h$ 使得 $f\ast g=h$。

记 $G,H$ 分别为 $g,h$ 的前缀和，那么可以推式子：

$$\begin{aligned} H(n)&=\sum_{i=1}^{n} h(n)=\sum_{i=1}^{n}\sum_{d\mid i} f(i)g\left(\frac{i}{d}\right)\\ &=\sum_{i=1}^{n}g(i)\sum_{d\leq n,d\mid i} f\left(\frac{i}{d}\right)=\sum_{i=1}^{n}g(i)\sum_{i=1}^{\lfloor\frac{n}{i}\rfloor} f(d)\\ &=\sum_{i=1}^{n} g(i)F\left(\left\lfloor\frac{n}{i}\right\rfloor\right)=g(1)F(n)+\sum_{i=2}^{n}g(i)F\left(\left\lfloor\frac{n}{i}\right\rfloor\right) \end{aligned}$$

故：

$$F(n)=\frac{1}{g(1)}\left(H(n)-\sum_{i=2}^{n}g(i)F\left(\left\lfloor\frac{n}{i}\right\rfloor\right)\right)$$

如果我们能够快速求出 $G(n)$ 以及 $H(n)$，那么我们就可以通过整除分块求后面的和式（注意和式中同样涉及到 $F$，可以向下递归并记忆化）的方法来求出 $F(n)$。

可以证明这一算法的时间复杂度是 $O(n^{2/3})$（假设求 $H(n)$ 的时间复杂度为 $O(1)$，并使用某些方法如线性筛，预处理前 $O(n^{2/3})$ 的函数值）。

例题

51Nod 1224 莫比乌斯函数之和：求 $\mu$ 的前缀和。

由于 $\mu\ast 1=\epsilon$，而 $1,\epsilon$ 的前缀和都是容易的，因此可以用杜教筛来做。时间复杂度 $O(n^{2/3})$。完整代码。

为了节省篇幅，这里只给出实现关键代码，下同：

i64 get_mu(i64 n){
    if(n <= BOUND) return mu[n];
    if(mp.count(n)) return mp[n];
    i64 ans = 1;
    for(i64 l=2,r;l<=n;l=r+1){
        r = n / (n / l);
        ans -= (r - l + 1) * get_mu(n / l);
    }
    return mp[n] = ans;
}

51Nod 1239 欧拉函数之和：求 $\varphi$ 的前缀和。

由于 $\varphi\ast 1=\mathrm{id}$，而 $1,\mathrm{id}$ 的前缀和都是容易的，因此也可以用杜教筛来做。时间复杂度 $O(n^{2/3})$。完整代码。

int get_phi(i64 n){
    if(n <= BOUND) return phi[n];
    if(mp.count(n)) return mp[n];
    int res = (((__int128)n * (n + 1)) >> 1) % mod;
    for(i64 l=2,r;l<=n;l=r+1){
        r = n / (n / l);
        res = Sub(res, Mul((r - l + 1) % mod, get_phi(n / l)));
    }
    return mp[n] = res;
}

HDU 5608 function：给定定义域为 $\mathbb{N}$ 的函数 $f$，满足 $n^2-3n+2=\sum_{d\mid n}f(d)$，求 $f$ 的前缀和。

若令 $g(n)=n^2-3n+2$，则题目给出的等式等价于 $g=f\ast 1$，这是一个可以用杜教筛来处理的形式。

由于 $1$ 的前缀和是容易的，并且 $g$ 的前缀和：

$$\sum_{i=1}^{n} i^2-3i+2=\frac{1}{3} \left(n^3-3 n^2+2 n\right)$$

也是容易求出的。

唯一的难点在于如何求前 $O(n^{2/3})$ 的 $f$ 的前缀和。注意到 $g=f\ast 1$ 可以改写为 $f=g\ast 1^{-1}$，而 $1$ 的狄利克雷生成函数为 $\zeta(z)$，它的逆 $\frac{1}{\zeta(z)}$ 是 $\mu$ 的生成函数。故 $f=g\ast \mu$，可以暴力筛求出（这个过程也被称为狄利克雷差分）。

故可以用杜教筛求 $f$，时间复杂度 $O(n^{2/3}\log n)$。完整代码

int get_f(int n){
    if(n <= BOUND) return f[n];
    if(mp.count(n)) return mp[n];
    int res = Mul(Mul(n, Add(Sub(Mul(n, n), Mul(n, 3)), 2)), inv3);
    for(int l=2,r;l<=n;l=r+1){
        r = n / (n / l);
        res = Sub(res, Mul(r - l + 1, get_f(n / l)));
    }
    return mp[n] = res;
}

P4318 完全平方数： 求第 $n$ 小的无平方因子数。

先二分，然后变成了求 $\mu^2$ 的前缀和。这东西有一个非常容易的基于容斥的做法，和本文无关，故不展开，这里仅给出杜教筛做法。

对于 $\mu^2$，它的狄利克雷生成函数是什么呢？首先 $f(n)=\mu^2(n)$ 显然是一个积性函数，因此可以得到：

$$\mathbf{F}(z)=\prod_{p\in\mathbb{P}}\sum_{i\geq 0} f(p^i)p^{-iz}=\prod_{p\in\mathbb{P}}1+p^{-z}=\prod_{p\in\mathbb{P}}\frac{1-p^{-2z}}{1-p^{-z}}=\frac{\zeta(z)}{\zeta(2z)}$$

故它的狄利克雷生成函数为 $\frac{\zeta(z)}{\zeta(2z)}$，于是杜教筛可以构造两个函数，$g,h$，$g$ 的狄利克雷生成函数为 $\zeta(2z)$，$h$ 的狄利克雷生成函数为 $\zeta(z)$。

$h=1$ 是显然的，那 $g$ 是什么呢，换句话说 $\zeta(2z)$ 是谁的狄利克雷生成函数呢？这是一个值得考虑的问题。

考察 $\zeta(z)$ 的一个等价形式：

$$\zeta(z)=\prod_{p\in\mathbb{P}}\sum_{i\geq 0} p^{-iz}$$

将 $z$ 替换为 $2z$，可以得到：

$$\zeta(z)=\prod_{p\in\mathbb{P}}\sum_{i\geq 0} p^{-2iz}=\prod_{p\in\mathbb{P}}\sum_{i\geq 0}[2 \mid i] p^{-iz}$$

也就是说 $g(p^i)=[2 \mid i]$，又因为 $g$ 应当是一个积性函数，所以自然得出若 $n$ 为完全平方数，则 $g(n)=1$，否则 $g(n)=0$。

现在 $g,h$ 都构造好了，要求 $f$ 的前缀和，必须求出 $g,h$ 的前缀和，$h$ 的前缀和是容易的，$g$ 的前缀和就是 $\lfloor\sqrt{n}\rfloor$ 也是容易的。

时间复杂度 $O(n^{2/3}\log n)$，完整代码。

int get_f(int n){
    if(n <= BOUND) return f[n];
    if(mp[n]) return mp[n];
    int ans = n;
    for(int l=2,r;l<=n;l=r+1){
        r = n / (n / l);
        int d = sqcnt(r) - sqcnt(l - 1);
        if(d) ans -= get_f(n / l) * d; // 注意这里有一个优化，参考 https://lglg.top/598495
    }
    return mp[n] = ans;
}

P3768 简单的数学题：求 $\sum_{i=1}^{n}\sum_{j=1}^{n}ij\gcd(i, j)$。

看到这个形式，先进行欧拉反演：

$$\begin{aligned} &\sum_{i=1}^{n}\sum_{j=1}^{n}ij\gcd(i, j)=\sum_{i=1}^{n}\sum_{j=1}^{n}ij\sum_{d\mid i,d\mid j}\varphi(d)\\ =&\sum_{d=1}^{n}\varphi(d)\left(\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}id\right)^2=\sum_{d=1}^{n}\varphi(d)d^2\left(\frac{\lfloor\frac{n}{d}\rfloor^2(\lfloor\frac{n}{d}\rfloor+1)^2}{4}\right) \end{aligned}$$

于是只要求出 $\varphi\cdot \mathrm{id}_2$ 的前缀和，就可以用整除分块求出答案。

令 $f(n)=\varphi(n)\cdot n^2$，考虑它的狄利克雷生成函数：

$$\mathbf{F}(z)=\sum_{i\geq 1} \varphi(i)i^2\cdot i^{-z}=\sum_{i\geq 1}\varphi(i)i^{-(z-2)}=\mathbf{\Phi}(z-2)=\frac{\zeta(z-3)}{\zeta(z-2)}$$

故 $\mathbf{F}(z)=\frac{\zeta(z-3)}{\zeta(z-2)}$。而 $\zeta(z-3)$ 是 $\mathrm{id}_3$ 的生成函数，$\zeta(z-2)$ 是 $\mathrm{id}_2$ 的生成函数。这两个函数的前缀和都是容易的，时间复杂度 $O(n^{2/3})$，完整代码。

LibreOJ 6682 梦中的数论：求 $F(n)=\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}[(j\mid i) \land ((j + k)\mid i)]$。

先对内部的二重和式进行化简：

$$f(i)=\sum_{j=1}^{n}\sum_{k=1}^{n}[(j\mid i) \land ((j + k)\mid i)]=\sum_j \sum_{k\neq j} [j\mid i \land k\mid i]=\binom{d(i)}{2}=\frac{d^2(i)-d(i)}{2}$$

那么原式即为：

$$F(n)=\sum_{i=1}^{n} f(i)=\frac{1}{2}\sum_{i=1}^{n}d^2(i)-\frac{1}{2}\sum_{i=1}^{n}d(i)$$

$\sum_{i=1}^{n}d(i)$ 可以用整除分块解决，现在的关键问题是求 $\sum_{i=1}^{n}d^2(i)$。

如果你阅读《哈代数论》比较仔细的话，可以看到第 $279$ 页的定理 $304$ 提到了这个函数 $d^2$：

拉马努金定理：

$$\frac{\zeta^4(z)}{\zeta(2z)}=\sum_{i\geq 1} d^2(i)i^{-z}$$

证明的话比较简单，直接推式子即可：

$$\begin{aligned} \frac{\zeta^4(z)}{\zeta(2z)}&=\prod_{p\in\mathbb{P}}\frac{1-p^{-2z}}{(1-p^{-z})^4}=\prod_{p\in\mathbb{P}}(1+p^{-z})(1-p^{-z})^{-3}\\ &=\prod_{p\in\mathbb{P}} (1+p^{-z})\sum_{i\geq 0}(-1)^ip^{-zi}\binom{-3}{i}=\prod_{p\in\mathbb{P}} (1+p^{-z})\sum_{i\geq 0}p^{-zi}\binom{i+2}{i}\\ &=\prod_{p\in\mathbb{P}}1+\sum_{i\geq 1} p^{-iz}\left(\binom{i+2}{2}+\binom{i+1}{2}\right)=\prod_{p\in\mathbb{P}}1+\sum_{i\geq 1} p^{-iz}(i+1)^2 \end{aligned}$$

所以 $\frac{\zeta^4(z)}{\zeta(2z)}$ 是一个积性函数 $\xi$ 的生成函数，且 $\xi(p^i)=(i+1)^2$，则 $\xi(n)$ 就是它的唯一分解的次数加一的乘积的平方，也就是 $d^2(n)$，证毕。

利用拉马努金定理，我们凑出来了一个类似杜教筛的形式，$\zeta(2z)$ 是完全平方数判定函数的生成函数，这是容易求前缀和的。而 $\zeta^4(z)=(\zeta^2(z))^2$，即 $d\ast d$ 的生成函数，可以使用整除分块套整除分块实现。

时间复杂度 $O(n^{2/3}\log n)$（我是暴力预处理前 $O(n^{2/3})$ 的 $f$ 值），应该可以做的更好，完整代码。

Powerful Number 筛

Powerful Number 筛是杜教筛的扩展。

Powerful Number

一个正整数 $n$ 被称为 Powerful Number，当且仅当对于任意一个质数 $p$，若 $p\mid n$，则 $p^2\mid n$。

OEIS A001694 记录了关于 Powerful Number 的更多信息。下面的代码可以用于判定 $n$ 是否为 Powerful Number：

PowerfulNumberQ[n_] := AllTrue[FactorInteger[n][[All, 2]], # >= 2 &]

定理 1：对于任意一个 Powerful Number $n$，一定存在两个正整数 $a,b$，使得 $a^2b^3=n$。

证明：可以用构造法证明。具体地，取 $n$ 的唯一分解 $n=\prod p_i^{e_i}$。对于每一个 $p_i^{e_i}$，若 $2\mid e_i$，则令 $a\gets a\cdot p_i^{e_i}$，否则令 $b\gets b\cdot p_i^3,a\gets a\cdot p_i^{e_i-3}$。由于 $e_i\geq 2$，所以每一步乘上的都是整数。故存在这样的 $a,b$。

定理 2：$\leq n$ 的 Powerful Number 的数量为 $O(\sqrt{n})$。

证明：$\leq n$ 的 Powerful Number 的精确数量为：

$$\sum_{k=1}^{\lfloor\sqrt{n}\rfloor} \left\lfloor\sqrt[3]{\frac{n}{k^2}}\right\rfloor$$

适当调整得到：

$$\sum_{k=1}^{\lfloor\sqrt{n}\rfloor} \left\lfloor\sqrt[3]{\frac{n}{k^2}}\right\rfloor\sim \int_{1}^{\lfloor\sqrt{n}\rfloor}\left\lfloor\sqrt[3]{\frac{n}{x^2}}\right\rfloor dx\sim \int_1^{\sqrt{n}}\frac{n^{1/3}}{x^{2/3}} dx=-3\sqrt[3]{n}+3\sqrt{n}\sim O(\sqrt{n})$$

在后文中，我们使用 $\mathbb{Z}_+[a^2b^3]$ 来表示全体 Powerful Number 集合。

流程

现在我们要求出一个积性函数 $f$ 的前缀和，可以尝试构造两个积性函数 $g,h$ 使得 $f=g\ast h$。进一步地，我们限制 $\forall p\in\mathbb{P}, f(p)=g(p)$，也就是在质数取值上，$f,g$ 的值相同。令 $F,G,H$ 分别表示 $f,g,h$ 的前缀和。

根据狄利克雷卷积的定义，对于质数 $p$，我们有 $f(p)=g(p)h(1)+g(1)h(p)$，又因为 $f(p)=g(p),h(1)=g(1)=1$，所以 $h(p)=0$。又因为 $h$ 是积性函数，所以 $h(n)\neq 0$ 是 $n$ 为 Powerful Number 的充分（非必要）条件。

接着我们仿照杜教筛的方法来推式子：

$$\begin{aligned} F(n)&=\sum_{i=1}^{n}f(i)=\sum_{i=1}^{n}\sum_{d\mid i} h(d)g\left(\frac{i}{d}\right)\\ &=\sum_{d=1}^{n}h(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}g(i)=\sum_{d\leq n, d\in \mathbb{Z}_+[a^2b^3]}h(d)G\left(\left\lfloor\frac{n}{d}\right\rfloor\right) \end{aligned}$$

若 $G$ 容易求前缀和（注意这里如果使用杜教筛求前缀和，则总时间复杂度为 $O(n^{2/3}$），则只需要暴力枚举 $d$（由关于 Powerful Number 的定理 2 得知 $d$ 的数量为 $O(\sqrt{n})$），计算 $h(d)$ 的值即可。

如何求得 $h(d)$ 的值？由于 $h$ 是积性函数，因此可以尝试预处理所有 $h(p^e)$ 的值。我们需要预处理出的值的总数为 $O(\pi\left(\sqrt{n}\right)\log n)=O(\frac{\sqrt{n}}{\log n})$。

如果 $h(p^e)$ 的值是容易求解的，那么就可以做到 $O(\sqrt{n})$ 了，否则我们可以递推。具体地，根据 $f=g\ast h$ 可以得到：

$$f(p^c)=\sum_{i=0}^{c}h(p^{c-i})g(p^{i})$$

进而得到：

$$h(p^c)=f(p^c)-\sum_{i=1}^{c}h(p^{c-i})g(p^{i})$$

这样递推时间复杂度为 $O(\sqrt{n})$，接着暴力搜索 Powerful Number 的过程中就可以算出每一个 Powerful Number 对应的 $h$ 值了。

整理一下，Powerful Number 求积性函数 $f$ 的前缀和的流程如下：

1. 找到一个容易求前缀和的积性函数 $g$。
2. 预处理 $h(p^e)$ 的值。
3. 搜索 Powerful Number，并随之计算对应的 $h$ 值。
4. 欲求 $F(n)$，则暴力枚举 $\leq n$ 的所有 Powerful Number $d$，对 $h(d)G(\left\lfloor\frac{n}{d}\right\rfloor)$ 求和。

时间复杂度预处理 $O(\sqrt{n})$，单次查询 $O(\sqrt{n})$ 或 $O(n^{2/3})$（若需要杜教筛）。

实践

P5325 【模板】Min_25 筛：定义积性函数 $f$ 满足 $f(p^k)=p^k(p^{k}-1)$，求它的前缀和。

若 $p$ 为质数，则 $f(p)=p(p-1)$，我们需要构造一个积性函数 $g$，使得 $f(p)=g(p)$ 且 $g$ 的前缀和容易求解。那么很容易想到 $g(n)=n\varphi(n)$。现在只需要求出 $g$ 的前缀和，就可以用 Powerful Number 筛求出 $f$ 的前缀和。

不妨先求出 $g$ 的狄利克雷生成函数：

$$\mathbf{G}(z)=\sum_{i\geq 1}\varphi(i)i\cdot i^{-z}=\sum_{i\geq 1}\varphi(i)i^{-(z-1)}=\mathbf{\Phi}(z-1)=\frac{\zeta(z-2)}{\zeta(z-1)}$$

而 $\zeta(z-2),\zeta(z-1)$ 分别为 $\mathrm{id}_2$ 和 $\mathrm{id}$ 的生成函数，这两个数论函数都是容易求前缀和的，所以可以用杜教筛求出 $g$ 的前缀和。

时间复杂度 $O(n^{2/3})$。

完整代码。写的比较丑，常数很大，仅作参考。

LibreOJ 6053. 简单的函数：定义积性函数 $f$ 满足 $f(p^k)=p\oplus k$，其中 $\oplus$ 为异或运算，求它的前缀和。

若 $p$ 为质数，则：

$$f(p)=\begin{cases} 3& p=2\\ p-1& \text{otherwise} \end{cases}$$

那么构造积性函数 $g$ 时不妨按照奇偶性分别考虑，对于奇数，可以构造 $\varphi(n)$，对于偶数，可以构造 $3\varphi(n)$，也就是：

$$g(n)=\begin{cases} \varphi(n)& 2\nmid n\\ 3\varphi(n)& 2\mid n \end{cases}$$

那么现在的问题是求 $g$ 的前缀和，记 $\varphi$ 的前缀和为 $\Phi(n)$，则推一下式子：

$$\begin{aligned} G(n)&=\sum_{i=1}^{n}g(i)=\sum_{i=1}^{n}[2\mid n]3\varphi(n)+\sum_{i=1}^{n}[2\nmid n]\varphi(n)=\sum_{i=1}^{n}[2\mid n]2\varphi(n)+\Phi(n) \end{aligned}$$

令 $K(n)=\sum_{i=1}^{n}[2\mid n]\varphi(n)$，则原式为 $G(n)=\Phi(n)+2K(n)$，对 $K(n)$ 推式子：

$$\begin{aligned} K(n)&=\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}\varphi(2n)=\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}\varphi(n)\gcd(n,2)\\ &=2\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor} [2\mid n]\varphi(n)+\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor} [2\nmid n]\varphi(n)\\ &=G\left(\left\lfloor\frac{n}{2}\right\rfloor\right) \end{aligned}$$

于是得到 $G(n)=2G\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+\Phi(n)$。而 $\Phi(n)$ 可杜教筛求得，所以 $G(n)$ 也可以经过 $O(\log n)$ 次递归求得。注意时间复杂度单次仍然为 $O(\log n)$，只是整体上多了杜教筛的 $O(n^{2/3})$。

时间复杂度 $O(n^{2/3})$。码力不足，没有码，但愿推导过程没错。

Min_25 筛

Min_25 筛是一种是埃式筛的扩展，可以以 $O(\frac{n^{3/4}}{\log n})$ 的时间复杂度求出积性函数 $f(n)$ 的前缀和，要求：

• 对于质数 $p$，$f(p)$ 是一个关于 $p$ 的低阶多项式（严格来说应该是完全积性函数线性组合的形式）。
• 对于质数 $p$，$f(p^k)$ 可以快速求值。

可以发现大多数函数都满足这两个限制，因此 Min_25 筛是目前最实用的高级筛法。

记号约定

• $\tau(n)$ 表示 $n$ 的最小质因子。
• $p_i$ 表示第 $i$ 小质数，特别地，$p_0=1$。但与一般的质数定义相同地，不认为 $1$ 是质数。

质数前缀统计

Min_25 筛的第一部分是质数前缀统计问题，即：

给定完全积性函数 $f$ 和整数 $n$，令 $G(n)=\sum_{p\in\mathbb{P},p\leq n} f(p)$。

你需要对于所有 $x$，求出 $G\left(\left\lfloor\frac{n}{x}\right\rfloor\right)$。

这个问题看起来挺难做的，实际上也挺难做的。不过 min_25 告诉我们可以 dp，设 $S(n, m)=\sum_{i=1}^{n}[i\in\mathbb{P}\lor \tau(i)>p_m] f(i)$，即质数或最小质因子大于 $p_m$ 的函数值前缀和。

那这玩意怎么转移呢？我们考虑埃氏筛的过程，考虑 $S(n,m)$ 到 $S(n,m-1)$ 的变化量，那么肯定是多在了具有 $\tau(i)=p_m$ 的质因子上。

而这一部分的贡献怎么算？一种看起来比较合适的方法是 $f(p_m)S\left(\left\lfloor\frac{n}{p_m}\right\rfloor, m-1\right)$（注意这里是 $m-1$ 而不是 $m$，这是因为一个数可能可以连续除多次 $p_m$）。

但这样子是不对的，因为 $S\left(\left\lfloor\frac{n}{p_m}\right\rfloor, m-1\right)$ 还包括了全体质数，如果包含了 $<p_m$ 的质数，就不满足我们 $\tau(i)=p_m$ 的要求，所以要将这一部分减去。

可以得到下面的转移方程：

$$S(n,m)=S(n,m-1)-f(p_m)\left(S\left(\left\lfloor\frac{n}{p_m}\right\rfloor, m-1\right)-\sum_{j=1}^{m-1} f(p_j)\right)$$

值得注意的是，如果 $(p_m)^2>n$，那么 $\left\lfloor\frac{n}{p_m}\right\rfloor < m$，则 $S\left(\left\lfloor\frac{n}{p_m}\right\rfloor, m-1\right)-\sum_{j=1}^{m-1} f(p_j)=0$，因此此时 $S(n,m)=S(n,m-1)$。

整理一下：

$$S(n, m)=\begin{cases} S(n, m - 1) & (p_m)^2>n\\ S(n,m-1)-f(p_m)\left(S\left(\left\lfloor\frac{n}{p_m}\right\rfloor, m-1\right)-\sum\limits_{j=1}^{m-1} f(p_j)\right) & \text{otherwise} \end{cases}$$

边界 $S(n,0)=\sum_{i=2}^{n} f(i)$。

最后我们来着手解决原问题。设 $p_{s(n)}$ 表示最小的大于等于 $\sqrt{n}$ 的质数，那么不可能存在合数 $k\leq n$，使得 $\tau(k)>p_{s(n)}$，所以 $S(n,s(n))$ 就是答案 $G(n)$。

具体的实现方法会在随后的一道例题中给出。

分析一下时间复杂度，额，我好像一顿积分后没有分析出来，解析解带有一个 $\mathrm{ExpIntegralEi}$ 的东西，不是很会处理。

不过记住这个东西的时间复杂度是 $O(\frac{n^{3/4}}{\log n})$ 的就行了。

质数前缀统计的实践

LibreOJ 6235 区间素数个数 给定 $n$，求 $\pi(n)$。

构造完全积性函数 $f(n)=1$，然后沿用质数前缀统计的思路即可。时间复杂度 $O(\frac{n^{3/4}}{\log n})$。

可是大家不想看看具体怎么实现吗?

首先由于第二维最大可以达到 $\pi(\sqrt{n})$，于是需要筛 $[1,\sqrt{n}]$ 的质数。

void sieve(int n){
    for(int i=2;i<=n;i++){
        if(!vis[i]) pri[++tot] = i;
        for(int j=1;j<=tot&&1ll*i*pri[j]<=n;j++){
            vis[i * pri[j]] = 1;
            if(!(i % pri[j])) break;
        }
    }
}
sqn = sqrt(n);
sieve(sqn);

然后注意到由于经典结论 $\left\lfloor\frac{\left\lfloor\frac{n}{a}\right\rfloor}{b}\right\rfloor=\left\lfloor\frac{n}{ab}\right\rfloor$，故第一维实际上只有形如 $\lfloor\frac{n}{x}\rfloor$ 的值是有用的，这样的值只有 $O(\sqrt{n})$ 个。可以用你喜欢的方法（比如整除分块）求出来。由于这一维我们需要记录到 dp 数组中，所以可以提前从大到小标号（需要支持标号与原数互相转换，但是使用 map 太慢，可以根号分治，用两个数组记录）方便后面的处理：

int get(i64 x){ return x <= sqn ? rev[x] : revt[n / x]; }
for(i64 l=1,r;l<=n;l=r+1){
    r = n / (n / l), w[++wtt] = n / l;
    if(w[wtt] <= sqn) rev[w[wtt]] = wtt;
    else revt[n / w[wtt]] = wtt;
}

最后的 dp 只需要按照我们上面推导的式子做即可，注意可以滚动数组省掉第二维：

for(int i=1;i<=wtt;i++) f[i] = w[i] - 1;
for(int j=1;j<=tot;j++){
    for(int i=1;i<=wtt&&1ll*pri[j]*pri[j]<=w[i];i++) f[i] -= f[get(w[i] / pri[j])] - (j - 1);
}
cout << f[1] << '\n';

完整代码。

积性函数求和

接下来进入 Min_25 筛的第二部分。

刚刚我们解决了质数前缀统计问题，不过可惜的是它只能解决完全积性函数，而我们只要求质数的取值是一个低次多项式。不过稍作转化并不是难事，对于多项式 $\sum_{i=0}^{n} a_ix^i$，完全可以将 $x^i$ 看成一个（完全）积性函数，然后将每一个这样的 $x^i$ 的和计算出来，最后乘上系数相加即可。

于是我们可以求出 $F_p(n)$ 表示 $\leq n$ 的质数 $p$ 的 $f(p)$ 的值之和，现在需要求出积性函数前缀和。

Min_25 告诉我们可以沿用以前的思路，具体地，设 $S(n,m)=\sum_{i=2}^{n} [\tau(i)>p_m] f(i)$，即最小质因子大于 $p_m$ 的函数值和。为了利用之前的质数前缀统计，我们可以将质数和合数分开计算。

对于质数，我们可以发现答案就是 $F_p(n)-F_p(p_m)$，即 $>p_m$ 的全体质数的函数值和。

对于合数，这有点复杂，不过我们可以尝试枚举它的最小质因子和次数：

$$\sum_{\substack{k\in[m+1,\pi(n)]\\ p_k^2\leq n}} \sum_{e=1}^{\lfloor\log_{p_k} n\rfloor} f(p_k^e)\left(S\left(\left\lfloor\frac{n}{p_k^e}\right\rfloor,k\right)+[e>1]\right)$$

稍微解释一下这个二重和式。我们枚举最小质因子 $p_k$ 和次数 $e$ 后，$p_k^e$ 就和剩下的数互质了，因此根据积性函数性质，可以提出一个 $f(p_k^e)$，剩余的部分就自然是 $S\left(\left\lfloor\frac{n}{p_k^e}\right\rfloor,k\right)$​ 了。

那 $[e>1]$ 又是什么呢？我们发现 $S(n,m)$ 中是不包括 $f(1)=1$ 的，而单独的 $p_k^e$ 在 $e>1$ 处又是应该计入答案的（注意 $e=1$ 时 $p_k^e=p_k$​ 是质数而不是合数，不计入答案），所以需要额外补一下。

不妨整理一下：

$$S(n,m)=\begin{cases} 0& p_m>n\\ F_p(n)-F_p(p_m)+\sum\limits_{\substack{k\in[m+1,\pi(n)]\\ p_k^2\leq n}} \sum\limits_{e=1}^{\lfloor\log_{p_k} n\rfloor} f(p_k^e)\left(S\left(\left\lfloor\frac{n}{p_k^e}\right\rfloor,k\right)+[e>1]\right)& \text{otherwise} \end{cases}$$

于是我们好像就做完了！最后答案是 $S(n,0)+1$（记得加上最后的 $f(1)=1$​）。

可以证明这一段的时间复杂度仍然是 $O(\frac{n^{3/4}}{\log n})$。

实践

P5325 【模板】Min_25 筛：定义积性函数 $f$ 满足 $f(p^k)=p^k(p^{k}-1)$，求它的前缀和。

第一道 Min_25 筛题，侧重讲解一下如何实现。

首先很容易发现 $f(p)=p^2-p$，满足 Min_25 的适用条件，将 $f(p)$ 拆成两个完全积性函数之差 $\mathrm{id}_2,\mathrm{id}$ 先去做质数前缀统计，这一部分和区间素数个数一题类似，因此只对关键部分做出说明：

void sieve(int n){
    for(int i=2;i<=n;i++){ // 线性筛质数
        if(!vis[i]) pri[++tot] = i;
        for(int j=1;j<=tot&&1ll*i*pri[j]<=n;j++){
            vis[i * pri[j]] = 1;
            if(!(i % pri[j])) break;
        }
    }
    for(int i=1;i<=tot;i++){ // 预处理小范围的函数前缀和
        fp1[i] = Add(fp1[i - 1], pri[i]);
        fp2[i] = Add(fp2[i - 1], Mul(pri[i], pri[i]));
    }
}
int get(i64 x){ return x <= sqn ? rev[x] : revt[n / x]; } // 定位函数
sqn = sqrt(n);
sieve(sqn);
for(i64 l=1,r;l<=n;l=r+1){ // 找到所有形如 floor(n/x) 的数，并建立索引
    r = n / (n / l), w[++wtt] = n / l;
    if(w[wtt] <= sqn) rev[w[wtt]] = wtt;
    else revt[n / w[wtt]] = wtt;
}
for(int i=1;i<=wtt;i++){ // 准备初始值
    int wt = w[i] % mod;
    f1[i] = Sub(Mul(wt, Add(wt, 1), inv2), 1); // 记得减去 1
    f2[i] = Sub(Mul(wt, Add(wt, 1), Add(wt, wt, 1), inv6), 1);
}
for(int j=1;j<=tot;j++){ // 质数前缀统计形式的 dp
    for(int i=1;i<=wtt&&1ll*pri[j]*pri[j]<=w[i];i++){
        f1[i] = Sub(f1[i], Mul(pri[j], Sub(f1[get(w[i] / pri[j])], fp1[j - 1])));
        f2[i] = Sub(f2[i], Mul(pri[j], pri[j], Sub(f2[get(w[i] / pri[j])], fp2[j - 1])));
    }
}

接下来就是第二部分的 dp 了，我们直接枚举 $k,e$（$e$ 只需要隐式枚举即可，可以显式枚举 $p_k^e$），然后计算贡献。

int solve(i64 n, int m){
    if(pri[m] > n) return 0; // 特判一下
    int ans = Sub(Sub(f2[get(n)], fp2[m]), Sub(f1[get(n)], fp1[m])); // 计算质数处的取值
    for(int k=m+1;k<=tot&&1ll*pri[k]*pri[k]<=n;k++){
        bool fir = 1; // 标记一下 e == 1 是否成立
        for(i64 pw=pri[k],pwt=pri[k];pw<=n;pw*=pri[k],pwt=Mul(pwt,pri[k])){
            // 注意 solve(n / pw, k)，我们直接递归就好了
            ans = Add(ans, Mul(Mul(pwt, Sub(pwt, 1)), Add(solve(n / pw, k), !fir)));
            fir = 0;
        }
    }
    return ans;
}

完整代码。

SP34096 DIVCNTK - Counting Divisors (general)：给定 $k$，计算 $f(n)=d(n^k)$ 的前缀和。

对于质数 $p$，$f(p)=d(p^k)=k+1,f(p^e)=d(p^{ke})=ke+1$ 满足 Min_25 的适用条件，那么只需要证明 $f$ 是积性函数即可。

所幸这也是容易的，若 $\gcd(a,b)=1$，则 $\gcd(a^k,b^k)=1$，而 $d$ 是积性函数，故 $f$ 亦是积性函数。

所以可以大胆用 Min_25 筛完成，时间复杂度 $O(\frac{n^{3/4}}{\log n})$，完整代码。

UOJ 188 【UR #13】Sanrd：定义 $f(n)$ 表示 $n$ 的“非严格次大质因子”（具体可以参考原题面，若不存在则为 $0$），求 $f$ 的前缀和。

注意，本题中的 $f(n)$ 的定义可以参考下面的 Wolfram 代码：

SecondLargestPrimeFactor[n_] := Module[{factors},
  factors = Flatten[ConstantArray @@@ FactorInteger[n]];
  If[Length[factors] < 2, 0, (Reverse @ Sort[factors])[[2]]]
]

考虑到 $f$ 不是积性函数，所以不能直接套用 Min_25 筛积性函数的方法，不过作为一种强有力的工具，Min_25 仍然可以帮助我们分析。

考虑第二部分，我们同样设 $S(n,m)$ 表示 $S(n,m)=\sum_{i=2}^{n} [\tau(i)>p_m] f(i)$，现在的问题是如何转移？

对于质数部分，答案显然是 $0$。对于合数部分，当我们剥离出最小质因子及其次数 $p^e$ 后，如果它是次大质因子，那么会贡献 $p\max(\pi(\lfloor\frac{n}{p^e}\rfloor))-\pi(p - 1))$，即 $p\sim \frac{n}{p^e}$ 的所有质数都可以作为剩余部分。如果不是次大质因子，那么就直接递归，没有额外贡献。而 $\pi$ 是质数前缀统计，也是可以 Min_25 的。时间复杂度 $O(\frac{n^{3/4}}{\log n})$。

完整代码。