Min_25筛小记
command_block
·
·
个人记录
1.质数的 c 次幂前缀和
可以去 P6021 【模板】质数前缀统计 & Loj#6235. 区间质数个数 进行阶段性测试 , My Code
我们考虑借鉴埃式筛法的思想,逐渐使用质数将不合法的数筛去。
设 $p_{\min}(n)$ 为 $n$ 的最小质因子。特殊地，$p_{\min}(1)=+∞$。
设 $S_{n,k}$ 为（埃式筛法）筛除 $p_1\sim p_k$ 的倍数之后 $n$ 以内剩余的数。
即 $S_{n,k}=\big\{x\in N^+\big|\ x\leq n\text{ 且 }p_{\min}(x)>k\big\}
( 注意，S_{n,k} 不包括 p_1\sim p_k ，但包括 1 )
- 定理 : 合数 q 必有一个 \lfloor\sqrt{q}\rfloor 以内的因子。
因此,实现埃式筛的时候,只需要利用 \lfloor\sqrt{N}\rfloor 以内的质数来筛除,就能正确地得到 N 以内所有的质数。
设 \lfloor\sqrt{N}\rfloor 内共有 m 个质数。
令 $h(n,k)=\sum\limits_{x\in S_{n,k}}x^c$ ,即筛除 $k$ 轮之后 $n$ 以内剩余的数的 $c$ 次方和。
那么，$h(N,m)-1+\sum\limits_{p\in P_m}p^c$ 即为答案。
我们以 $k$ **从小到大**的方式，依次筛去“**最小素因子**为 $p_k$ 的数”，注意只筛到 $p_m$ 即可。
设 $D_{n,k}=\big\{x\in N^+\big|\ x\leq n\text{ 且 }p_{\min}(x)=k\big\}$ ,即埃式筛法 $k$ 轮中筛除的数。
按照定义有 $S_{n,k}=S_{n,k-1}-D_{n,k}$。
又能发现，对于 $x\in S_{\lfloor n/p_k\rfloor,k-1}$ 则 $p_k*x$ 最小素因子恰为 $p_k$，即 $p_k*x\in D_{n,k}$。
而且，若 $t\in D_{n,k}$ ，那么 $t/p_k$ 一定 $\in S_{\lfloor n/p_k\rfloor,k-1}$。
这给出一个双射（充要条件），即 $D_{n,k}=p_kS_{\lfloor n/p_k\rfloor,k-1}
综上可得如下关系式 ：
\large S_{n,k}=S_{n,k-1}-p_kS_{\lfloor n/p_k\rfloor,k-1}
由此得到 h 的递推式 :
h(n,k)=h(n,k-1)-p_k^ch(\lfloor n/p_k\rfloor,k-1)
边界 ： h(n,0)=\sum\limits_{i=1}^ni^c ,可以插值求出。
注意到我们在递推中需要利用 \lfloor n/p_k\rfloor 处的取值。
由整除经典结论，我们只用维护任意的 \lfloor N/d\rfloor 处的答案即可,这一共 O(\sqrt{N}) 个。
接下来我们讨论实现方法。
采用暴力实现,在每个质数处使用上述递推式,复杂度为:
质数个数 O(\frac{\sqrt{N}}{logN}) ,维护的值 O(\sqrt{N}) ,总复杂度为 O(\frac{N}{logN})。
当 p_k>\sqrt{n} 时，可推知 D_{n,k}=\{p_k\} ,于是 S_{n,k}=S_{n,k-1}-\{p_k\}。
\Rightarrow S_{n,k}+P_k=S_{n,k-1}+P_{k-1}
不妨令 S'_{n,k}=S_{n,k}+P_k ,改设 h(n,k)=\sum\limits_{i\in S'_{n,k}}i^c。
这样，当 p_k>\sqrt{n} 时，S'_{n,k}=S'_{n,k-1} ，无变化。
这样，只有筛 \leq \sqrt{n} 的质数才会影响到 h(n,\_) 的值。
当 p_k\leq\sqrt{n} 时 , 由 S_{n,k}=S_{n,k-1}-p_kS_{\lfloor n/p_k\rfloor,k-1}
$\Rightarrow S'_{n,k}=S'_{n,k-1}-p_k(S'_{\lfloor n/p_k\rfloor,k-1}-P_{k-1})+\{p_k\}$ （全部改写为 $S'$）
注意到 $S'_{p_{k-1},k-1}=P_{k-1}+1$ ,可替换为 ：
$\Rightarrow S'_{n,k}=S'_{n,k-1}-p_k(S'_{\lfloor n/p_k\rfloor,k-1}-S'_{p_{k-1},k-1})
这对应下面的递推式 ：
h(n,k)=h(n,k-1)-p_k^c\Big(h(\lfloor n/p_k\rfloor,k-1)-h(p_{k-1},k-1)\Big)
最终答案为 h(n,m)-1。
有 O(\frac{\sqrt{n}}{\log n}) 个质数会影响到 h(n,\_) 。取最大的 \sqrt{N} 个 n=\lfloor N/d\rfloor 积分 ：
总复杂度 O\bigg(\sum\limits_{d=1}^{\sqrt{N}}\frac{\sqrt{N/d}}{log(N/d)}\bigg)=O(\frac{N^{3/4}}{logN})。
该做法实战中最为常用。
后续更优做法可见相关文章②。
2.积性函数求和
-
问题概述 :
给出一个积性函数 F ,满足如下性质:
我们以 k 从大到小的方式,考虑“最小素因子为 p_k 的数”。
方便起见，设 S_{n,k} 为最小素因子 \geq p_k 的集合。
仿照前面 h 的求解方法,设 r(n,k)=\sum\limits_{i\in S_{n,k}}^nG(i)。
则答案为 r(N,1)。
枚举 p_t=p_{\min}(x)，再枚举 x 中 p_k 的次数 c ，对于符合该要求的 x 计算贡献。
可得 r(n,k)=\sum\limits_{t=k}^{p_t\leq n}\sum\limits_{c=1}F(p_t^c)r\big(\lfloor x/p_t^c\rfloor,t+1\big)
只需枚举到 $\sqrt{n}$ ，对于 $p_k>\sqrt{n}$ 的情况，符合条件的 $x$ 只有 $p_k$ 本身，可以使用前面求出的素数部分和。
直接暴力搜索，不需要记忆化。
在 $10^{12}$ 内，复杂度可以视为 $O\Big(\frac{N^{3/4}}{\log N}\Big)$ ，证明见 2018 年候选队论文。
- **例题①** : [Loj#6053. 简单的函数](https://loj.ac/problem/6053)
当 $p$ 为奇质数时 $G(p)=p{\ \rm xor\ }1=p-1$。特殊地，$G(2)=3$。
[评测记录](https://loj.ac/submission/991601)
- **例题②** : [Uoj#188. 【UR #13】Sanrd](https://uoj.ac/problem/188)
次大质因子貌似和上面提到的积性函数求和没什么关系……
设 $f(n)$ 为 $n$ 的非严格次大质因子。
设 $r(n,k)$ 为 $\sum\limits_{i\in S_{n,k}}f(i)$。
设 $h[l,r]$ 为 $[l,r]$ 区间内的质数个数。
仍然考虑枚举 $p_t=p_{\min}(x)$，再枚举 $x$ 中 $p_k$ 的次数 $c$ ，对于符合该要求的 $x$ 计算贡献。
分两类讨论 ：
若 $x=p_t^{c_1}p_l\ (t\leq l)$ ，则 $f(x)=p_t$ 。
若 $x=p_t^cy$，且 $y$ 的质因子次数 $\geq 2$ 那么 $f(x)=f(y)
可得 r(n,k)=\sum\limits_{t=k}^{p_t\leq n}\sum\limits_{c=1}\Big(r\big(\lfloor x/p_t^c\rfloor,t+1\big)+p_t*h\big[p_t,\lfloor n/p_t^c\rfloor\big]+[c>1]\Big)
由于质数的贡献为 0 ，可以省去第一部分。
评测记录