Min_25 筛
喵仔牛奶
·
·
算法·理论
适用范围
筛出积性函数前缀和，即 \sum_{i=1}^{n}f(i)。
条件：
- 对于素数 p，f(p) 可以被表示为 \sum c_if'_i(p) 的形式，其中 f'_1(p),f'_2(p),\cdots 是完全积性函数，且 f'_1(p),f'_2(p),\cdots 的前缀和可以快速求出。
- 对于素数的幂次 p^k，f(p^k) 可以快速求出。
时间复杂度是 \mathcal{O}(\dfrac{n^{3/4}}{\log n})。由于喵仔牛奶太菜，下文不提及复杂度的分析。
做法
Step 1
设 f(p)=f'_1(p)+f'_2(p)。
用线性筛求出 1\sim \sqrt n 的素数的 f'_1(p),f'_2(p) 的值，记其中素数有 ct 个。
Step 2
设 g(n,x)=\sum_{i=1}^{n}[i\in P\lor \min_{p\mid i}p>P_x]f'(i)。
有转移方程：
g(n,x-1) & P_x^2>n \\
g(n,x-1)-f'(P_x)\times(g(\lfloor\dfrac{n}{P_x}\rfloor,x-1)-\sum_{i=1}^{x-1}f'(P_i)) & P_x^2\le n
\end{cases}
解释：
- 考虑由 g(n,x-1) 推来，要减去的就是 \min_{p\mid i}p=x 的数的贡献。
- 可以发现，要减去的就是最小的质因子是 P_x 的合数。如果 P_x^2>n，没有没有多算的合数，不用变。
- 否则，把这些合数除以一个 P_x，对应的就是 g(\lfloor\dfrac{n}{P_x}\rfloor,x-1)。
- 但是我们把 <P_x 的质数算进去了，对于 p<P_x 而言，p\times P_x 中的最小质因子是 p，在 g(n,x-1) 中计入，所以需要减去它们，即 \sum_{i=1}^{x-1}f'(P_i)。
- 此处直接乘 f'(P_x) 用了完全积性函数的性质，如果不是完全积性函数但可以求出 g 仍然可以使用 Min_25 筛。
由于 \lfloor\dfrac{\lfloor\dfrac{n}{a}\rfloor}{b}\rfloor=\lfloor\dfrac{n}{ab}\rfloor，所以 n 只有 \mathcal{O}(\sqrt{n}) 种。具体地，n 总是可以被表示为 x 或 \lfloor\dfrac{n}{x}\rfloor，其中 x\le\sqrt{n}。
考虑初值 g(n,0) 如何求，这个相当于求 \sum_{\boldsymbol{i=2}}^{n}f'(i)（注意下界），我们之前已经要求了 $f'
注意到 $P_{ct}$ 是最大的满足 $P_{x}^2\le n$ 的素数，所以 $g(n,ct)=\sum_{i=1}^{n}[i\in P]f'(i)$，即**前缀所有素数的 $\boldsymbol{f'}$ 和**。
注意到我们是 $f(p)=f'_1(p)+f'_2(p)$，对 $f'_1,f'_2$ 分别求出 $g_1(n,x),g_2(n,x)$ 后，我们令 $g(n,x)=g_1(n,x)+g_2(n,x)$。
## Step 3
我们设 $S(n,x)=\sum_{i=1}^{n}[\min_{p\mid i}p>P_x]f(i)$。
$$S(n,x)=g(n,ct)-\sum_{i=1}^{x}f'(P_i)+\sum_{i\in[x+1,ct]}\sum_{j\ge 1,P_i^j\le n}f(P_i^j)\times(S(\lfloor\dfrac{n}{P_i^j}\rfloor,i)+[j>1])$$
解释：
- 考虑素数的贡献，显然是 $g(n,ct)-\sum_{i=1}^{x}f'(P_i)$，后面的减法减去了 $\le x$ 的素数的贡献。**前面的计算都是为了这步。**
- 要考虑的所有数的最小质因子都 $>P_x$，考虑枚举最小质因子 $P_i$ 与它的次数 $j$，贡献即为 $f(P_i^j)(S(\lfloor\dfrac{n}{P_i^j}\rfloor,i)+[j>1])$。后面的 $[j>1]$ 是因为我们不考虑 $1$，所以多了 $P_i^j$ 的贡献。
答案即为 $S(n,0)+1$。
## 题目
### P4213 【模板】杜教筛
莫比乌斯函数：
- 对于素数 $p$，$\mu(p)=-1$，令 $f'(x)=1$；
- 对于 $p^k$，$\mu(p^k)=0$。
欧拉函数：
- $\varphi(p)=p-1$，令 $f'_1(x)=1,f'_2(x)=x$；
- $\varphi(p^k)=p^k(1-\dfrac{1}{p})$。
### P5325 【模板】Min_25 筛
- 对于素数 $p$，$f(p)=p(p-1)$，令 $f'_1(x)=x,f'_2(x)=x^2$。
- 对于 $p^k$，$f(p^k)=p^k(p^k-1)$。
### [24.11.17 模拟赛] 集合操作
答案为 $\sum_{i=1}^{n}\frac{1}{d_i}$。
- 对于素数 $p$，$\frac{1}{d_p}=\frac{1}{2}$，令 $f'(p)=1$。
- 对于 $p^k$，$\frac{1}{d_{p^k}}=\frac{1}{k+1}$。