Min_25 筛入门

min_25 筛适用于求积性函数前缀和，并且能够找到一个完全积性函数使得两个函数质数处的取值相同。

$$\gdef\Prime{\mathcal{P}}$$

记号说明

1. $\Prime$表示质数集合。

2. 设$p_i$表示从小到大第$i$个质数（$p_1=2$）。

3. $\Prime_i$表示小于等于$i$的质数构成的集合，即$\Prime_i=\{x\le i|x\in \Prime\}$。
4. $Q(n)$表示$n$的最小质因子。

前提条件

定义$f(n)$是一个积性函数。$f'(n)$是完全积性函数，且$f'$与$f$在质数处的取值相同，即$\forall x\in \Prime,f'(x)=f(x)$，且$f'$要能快速计算前缀和。

算法摘要

简单描述一下筛法的步骤：

1. 我们的目标是求$F(n)=\sum_{i=1}^nf(i)$。
2. 由于$f(i)$是积性函数，因此$f(1)=1$。于是转化为$F(n)=1+\sum_{i=2}^nf(i)$。
3. 我们先求出$G(n)=\sum_{i\in \Prime_n}f'(i)$，表示所有质数处的取值。
4. 然后统计所有合数的贡献，再加上$G(n)$和$1$就是$F(n)$。

第一部分

定义

$$g(i,n)=\sum_{x\in \Prime_n\cup\{x\le n|Q(x)> p_i \}} f'(x)$$

表示满足$x$是$n$以内的质数或者最小质因子大于$p_i$的$f'(x)$的和。我们可以用埃氏筛来理解这个定义，相当于目前筛到了质数$p_i$，最小质因子大于$p_i$的数则没有被筛到。

显然$G(n)=g(n,n)$。并且$g(i,1)=0$。边界情况$g(0, i) = \sum_{j=2}^i f'(j)$。因此为了计算$g(0, i)$，$f'$需要支持快速计算前缀和。

接下来考虑递归计算$g(i,n)$。讨论$p_i$与$n$的关系。

如果$p_i^2>n$，意味着$n$以内不存在最小质因子大于等于$p_i$的合数。即$\{x\le n|Q(x)> p_{i-1} \}=\{p_i\}$。因此得到

$$g(i,n)=g(i-1,n)\quad (p_i^2>n)$$

如果$p_i^2\le n$，那么相当于我们只需要在$g(i-1,n)$里减掉多余的部分就可以得到$g(i,n)$。具体地，我们减掉$Q(x)=p_i$的合数就可以了。这部分的和可以表示为（这里用到了$f'$的完全积性）

$$\sum_{p_i|x,x\le n} f'(p_i)f'\left(\frac{x}{p_i}\right)\left[Q\left(\frac{x}{p_i}\right)\ge p_i\right]$$

另一方面，后者可以用$g$表示：

$$\begin{aligned} &\sum_{p_i|x,x\le n} f'\left(\frac{x}{p_i}\right)\left[Q\left(\frac{x}{p_i}\right)\ge p_i\right]\\ =&\sum_{x\le \frac{n}{p_i}} f'(x)[Q(x)\ge p_i]\\ =&g\left(i-1,\left\lfloor\frac{n}{p_i}\right\rfloor\right)-\sum_{j=1}^{i-1}f'(p_j) \end{aligned}$$

于是得到

$$g(i,n)=g(i-1,n)-f'(p_i)\left(g\left(i-1,\left\lfloor\frac{n}{p_i}\right\rfloor\right)-\sum_{j=1}^{i-1}f'(p_j)\right)\quad (p_i^2\le n)$$

记$h(i)=\sum_{j=1}^if(p_j)=\sum_{j=1}^if'(p_j)$，则汇总两个转移得到

$$g(i,n)=\begin{cases} g(i-1,n)& (p_i^2>n)\\ g(i-1,n)-f'(p_i)\left(g\big(i-1,\lfloor\frac{n}{p_i}\rfloor\big)-h(i-1)\right)& (p_i^2\le n) \end{cases}$$

容易发现，我们并不需要求出$g(n,n)$。设$k$满足$p_{k+1}^2>n,p_{k}^2\le n$。那么显然$G(n)=g(n,n)=g(k,n)$。

因此我们线性筛预处理出$p_1,p_2,\cdots,p_k$，然后预处理出$h(x),x\in[1,k]$，这样就可以计算$g(k,n)$了。实现可以使用滚动数组。

这部分的时间复杂度约为是$O\Big( \frac{n^{\frac{3}{4}}}{\ln n} \Big)$。

第二部分

定义

$$S(i,n)=\sum_{x\le n,Q(x)\ge p_i}f(x)$$

即所有最小质因子大于等于$p_i$的$f(x)$的和。那么可以得到$F(n)=f(1)+S(1,n)=1+S(1,n)$。

同样考虑求出$S(i,n)$的递归式。我们把质数和合数的贡献分开考虑。

质数部分的贡献显然是$G(n)-h(i-1)$。

对于合数部分，我们枚举它的最小质因子，假设是$p_j(j\ge i)$。然后枚举$p_j$在合数中出现的次数，假设为$e$。那么剩下的部分如果大于$1$，就表示为$S\left(i+1,\left\lfloor\frac{n}{p_j^e}\right\rfloor\right)$。如果一个合数只含有质因子$p_j$，那么表示为$p_j^{e+1}$就行了。这时的贡献就是$f(p_j^{e+1})$。

综上得到

$$S(i,n)=G(n)-h(i-1)+\sum_{i\le j,p_j^2\le n}\sum_{e\ge 1,p_j^{e+1}\le n}f(p_j^e)S\left(i+1,\left\lfloor\frac{n}{p_j^e}\right\rfloor\right)+f(p_j^{e+1})$$

在实现的时候直接递归即可。

这个部分的复杂度是$O(n^{1-\epsilon})$的。

小结

第一部分的$g$本质上用于处理完全积性函数在质数处取值的前缀和问题。换言之对于$f$在质数处的表达式$f(p)$，只要能将其分解为若干个完全积性函数的和的形式，那么就可以分别使用这一过程处理。

第二部分的核心部分是递归，这要求我们能快速计算$f$在质数幂处的取值$f(p^e)$，这样利用第一个过程里预处理的部分就可以筛出来。

当$n\le 10^{13}$时，Min_25 筛的总时间复杂度是$O\Big( \frac{n^{\frac{3}{4}}}{\ln n} \Big)$的。

模板代码