min25筛详解

Min25筛详解

min25筛有什么用？

目的： 求出$\sum_{i-1}^Nf(i)$的前缀和，其中前置条件为

• $f(i)$ 当i为素数时，能够用$i^k$表达，例如$f(i)=i^1+i^2+i^3$等形式，常见的有$\phi \quad \mu$函数。

• $f(i)$是积性函数

怎么求？

分两步走

• 处理素数
• 处理合数

处理素数

素数部分

$$\sum_{i=1}^N[i \in prime] f(i)$$

既然素数的函数值能够简单的被表达那么肯定可以求出来。

1. 设前缀和$sum_i$为

   $sum_i = \sum_{i-1}^if(prime_i)$ 即前i个素数的函数值的前缀和

2. 设函数$g(N,i)$

   $$g(N,i) = \sum_{j=1}^N[j \in prime \mid Min_j > prime_i]*f(j)$$

   通俗的来说，$g(N,i)$就表示$N$以内的在埃拉特斯特尼筛算法进行第$i$轮后尚未被筛去的数的函数值的和。

   显然我们要求的就是

   $$g(N,\infty) = \sum_{i=1}^N[i \in prime] f(i)$$

   其实不用到达无穷大，最大到达的为$\sqrt{n}$内的素数个数

考虑怎么求出这个式子,考虑i从小往大递推，g(N,0)的时候发现就是一个简单的幂次前缀和，这里一般可以用公式来做。

$$g(N,0) = sum(N)$$

考虑如何从$g(N,i-1) => g(N,i)$

埃筛的思路

• $prime_{i}^2>N$时，显然已经筛不出任何的数

• $prime_i^2 <=N$时，考虑$N$中被$prime_i$筛去的数(没有被$prime_i$小的素数筛掉的数中）

  $$g(N,i) = g(N,i-1) - f(prime_i) * (g(\lfloor\frac{N}{prime_i} \rfloor, i-1 ) - sum_{i-1})$$

  解释一下上面这个式子，假设$N=16 , i = 1$时，式子变为

  $$g(N,i) = g(N,i-1) - f(2) * (g(8, 0 ))$$

  很显然$g(8,0) f(2)$此时为$(f(1)+f(2)+\cdots +f(8)) f(2)$,因为是积性函数，所以就相当于把2的倍数的值给全都算出来了给删除了。所以最后的出g的递推式为

  $$g(N,i) = \begin{cases} g(N,i-1)\quad \quad prime_i^2>N\\ g(N,i-1) - f(prime_i) * (g(\lfloor\frac{N}{prime_i} \rfloor, i-1 ) - sum_{i-1}) \quad \quad \quad prime_i^2 <=N \end{cases}$$

这个式子被证明复杂度在$O(\frac{n^{\frac{3}{4}}}{logN})$的

处理合数

再明确一次我们需要求的答案

$$\sum_{i=1}^N f(i)$$

此时我们已经有了

$$\sum_{i=1}^N[i \in prime]f(i)$$

且f(i)是积性函数，那么就很方便了

定义一个函数

$$S(N,i) = \sum_{j=1}^N[Min_j > prime_i] * f(i)$$

即满足所有最小质因子大于等于$prime_i$的$f(i)$的和,埃筛i轮后剩下的值

将$S(N,i)$分为两部分，刚刚的素数部分我们已经解决了

$$S(N,i) = g(N,\infty) - sum_{i-1} + 合数$$

合数部分怎么解决？

因为$f$是一个积性函数，所以我们枚举合数的最小质因子及其出现的次数即可

$$\sum_{j=i}^{prime_j^2<=N}\sum_{k=1}^{prime_j^k<=N}(S(\lfloor \frac{N}{prime_j^k} \rfloor,i-1)*f(prime_j^k) +f(prime_j^{k+1}))$$

解释一下这个很长的和式

第一部分枚举从第i个质数开始枚举，因为当前是第i轮$prime_j$

第二部分则枚举这个质数的幂次

后面一部分跟求$g$的思路是类似的，最后加上$f(prime_j^{k+1})$是因为当$\frac{N}{prime_j^k}=0$时，进入的话会返回0，所以在外面加上，例如S(1,0)时，我们会直接返回0，f(8)则没有计算到。

完了，min25筛结束了

主要的解题思路为：

• 分块
• 处理素数的前缀和
• 写S函数
• 求答案

因为这里用到的所有的数都是$\frac{N}{i}$的形式，所以很显然的可以进行分块处理。

模板题

LOJ 6053