筛子学习笔记
stardust_Ray
·
2024-07-22 18:23:52
·
算法·理论
大部分是抄 OI-wiki 和题解的，作为整理思路用
前置知识
质数与合数的定义，初等数学。
欧拉函数、莫比乌斯函数的定义。
质数筛
目标：筛出 1~n 中的所有质数
埃式筛
过程
对于筛到的每一个质数，枚举它的所有倍数，将它的倍数全部标记为合数。可以证明时间复杂度为 O(n\log \log n)
实现
const int N=1e7+5;
bool vis[N];
for(int i=2;i<=n;i++)
if(!vis[i])
for(int j=2*i;j<=n;j+=i)
vis[j]=1
埃式筛存在许多卡常的方法：
由于除了 2 以外的质数均为奇数，可以使常数减半
将 bool 数组改为 bitset
欧拉筛
过程
由于在埃式筛中我们会重复标记大量的节点，所以我们考虑如何让每个合数只被标记一次，即只被最小的质数标记。
考虑从小往大扫描 i \in [2,n]，每次枚举从小往大质数集合，更新合数标记。如果 i \bmod prime_j=0，那么就停止循环。那么当一个合数被标记的时候，一定是被最小的质因子标记。
证明：设当前合数为 x=p_1^{a_1}p_2^{a_2}...p_k^{a_k},p_1 实现 int p[N],tot;bool vis[N]; for(int i=2;i<=n;i++){ if(!vis[i]) p[++tot]=i; for(int j=1;j<=tot&&i*p[j]<=n;j++){ vis[i*p[j]]=1; if(i%p[j]==0) break; } } 应用 欧拉筛可以用来线性的筛出大部分积性函数的值。 欧拉函数 根据欧拉函数的性质 \varphi(ij)=\dfrac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))} 当 i 与 p_j 互素时，\varphi(ip_j)=\varphi(i)\varphi(p_j) 当 \gcd(i,p_j)=p_j 时，\varphi(ip_j)=\dfrac{\varphi(i)\varphi(p_j)p_j}{\varphi(p_j)}=\varphi(i)p_j 实现： int p[N],tot,phi[N];bool vis[N]; phi[1]=1; for(int i=2;i<=n;i++){ if(!vis[i]) p[++tot]=i,phi[i]=i-1; for(int j=1;j<=tot&&i*p[j]<=n;j++){ vis[i*p[j]]=1; if(i%p[j]==0){ phi[i*p[j]]=phi[i]*p[j]; break; }phi[i*p[j]]=phi[i]*phi[p[j]]; } } 莫比乌斯函数 根据莫比乌斯函数的定义可得： \mu(ip_j)=\begin{cases} 0&,\gcd(i,p_j)=p_j \\ -mu(i)&,\text{otherwise}\end{cases} 实现： int p[N],tot,mu[N];bool vis[N]; phi[1]=1; for(int i=2;i<=n;i++){ if(!vis[i]) p[++tot]=i,mu[i]=-1; for(int j=1;j<=tot&&i*p[j]<=n;j++){ vis[i*p[j]]=1; if(i%p[j]==0){ mu[i*p[j]]=0; break; }mu[i*p[j]]=-mu[i]; } } 积性函数前缀和 考虑积性函数 f，快速计算出 S(n)=\sum\limits_{i=1}^{n}f(i) 杜教筛 考虑构造出一个 S(n) 和 S(\lfloor\frac{n}{i}\rfloor) 的递推式。 对于任意一个积性函数 g，满足 \sum\limits_{i=1}^n(f*g)(i)&=\sum\limits_{i=1}^n\sum\limits_{d|i}f(\frac{i}{d})g(d) \\ &=\sum\limits_{d=1}^ng(d)\sum\limits_{i=1}^{\frac{n}{d}}f(i) \\ &=\sum\limits_{i=1}^ng(i)S(\lfloor\frac{n}{i}\rfloor) \end{aligned} 提取出右式 i=1 时的一项，剩余移到左边，得到 g(1)S(n)=\sum_{i=1}^n(f*g)(i)-\sum\limits_{i=2}^ng(i)S(\lfloor\frac{n}{i}\rfloor) 也就是说，我们现在是需要构造出一个 g 使得可以快速计算 (f*g) 和 g 的前缀和即可快速地求出 S(n)。 可以证明，如果上述两项均可以 O(1) 计算，那么时间复杂度为 O(n^{\frac{3}{4}})。如果预处理 n^{\frac23} 以内的值和前缀和，则可以优化到 O(n^{\frac23})。 Tips：事实上上文并没有用到 f 是积性函数的性质，所以它可以用来做 f 不是积性函数的情况。 求莫比乌斯函数前缀和 根据 \sum\limits_{d|i}\mu(d)=\epsilon(i)=\begin{cases}1,i=1\\0,\text{otherwise}\end{cases}. 代入杜教筛公式 S(n)=1-\sum\limits_{i=2}^{n}S(\lfloor\frac{n}{i}\rfloor) 数论分块即可。 求欧拉函数前缀和 根据 \sum\limits_{d|i}\varphi(d)=i，代入杜教筛公式 S(n)=\dfrac12n(n+1)-\sum\limits_{i=2}^{n}S(\lfloor\frac{n}{i}\rfloor) 数论分块即可。 实现 bool vis[N+5];int p[N],tot,phi[N+5],mu[N+5];ll sp[N+5],sm[N+5]; unordered_map void init(int n){ //预处理 n^{2/3} 以内的答案 phi[1]=1;mu[1]=1; for(int i=2;i<=n;i++){ if(!vis[i]) p[++tot]=i,phi[i]=i-1,mu[i]=-1; for(int j=1;j<=tot&&i*p[j]<=n;j++){ vis[i*p[j]]=1; if(i%p[j]==0){ phi[i*p[j]]=phi[i]*p[j]; mu[i*p[j]]=0;break; }phi[i*p[j]]=phi[i]*(p[j]-1); mu[i*p[j]]=-mu[i]; } }for(int i=1;i<=n;i++) sp[i]=sp[i-1]+phi[i],sm[i]=sm[i-1]+mu[i]; } ll SumPhi(ll x){ if(x<=N) return sp[x]; if(Phi.count(x)) return Phi[x]; //记忆化 Phi[x]=(ll)x*(x+1)/2; for(ll l=2,r;l<=x;l=r+1){ //数论分块 r=x/(x/l); Phi[x]-=(r-l+1)*SumPhi(x/l); }return Phi[x]; } ll SumMu(ll x){ if(x<=N) return sm[x]; if(Mu.count(x)) return Mu[x]; //记忆化 Mu[x]=1; for(ll l=2,r;l<=x;l=r+1){ //数论分块 r=x/(x/l); Mu[x]-=(r-l+1)*SumMu(x/l); }return Mu[x]; } PN 筛 Powerful Number 令 x 质因数分解后为 p_1^{a_1}p_2^{a_2}...p_k^{a_k}，定义 x 为 PN 当且仅当 \forall i \in [1,k],a_i>1 性质 1：所有的 PN 都可以表示为 a^2b^3 的形式。 性质 2：n 以内的 PN 只有 O(\sqrt{n}) 个。 过程 构造积性函数 g 满足 g(p)=f(p)，令 G(n)=\sum\limits_{i=0}^ng(i)。构造函数 h=f/g，即 g*h=f，所以 h(1)=1。容易证明 h 是积性函数。 对于素数 p，f(p)=g(1)h(p)+g(p)h(1)，又由于 g(p)=g(1)，所以 h(p)=0。又因为 h 是积性函数，所以 h 只在 PN 处有值。 \begin{aligned} S(n)&=\sum\limits_{i=1}^n\sum\limits_{d|i}h(d)g(\dfrac{i}{d}) \\ &=\sum\limits_{i=1}^nh(i)\sum\limits_{j=1}^{\frac{n}{d}}g(j) \\ &=\sum\limits_{i=1}^nh(i)G(\lfloor\dfrac{n}{i}\rfloor) \\ &=\sum\limits_{i=1,i \in PN}^nh(i)G(\lfloor\dfrac{n}{i}\rfloor) \end{aligned} 为了得到 h 的值，我们事实上只用得到 h(p^c) 的值。对于这个问题，我们一般有 2 种方法，一种是直接推出 h(p^c) 和 p,c 之间的关系式；另一种是由于 f=g*h，所以 f(p^c)=\sum\limits_{i=0}^{c}g(p^i)h(p^{c-i})，移项得到 h(p^c)=f(p^c)-\sum\limits_{i=1}^{c}g(p^i)h(p^{c-i})，暴力求解即可。对于第二种方法，得到 h(p^c) 的时间复杂度为 O(\sqrt{n}\log n)，搜索 h(i) 的复杂度为 O(\sqrt{n})。 关于计算 G(\lfloor\dfrac{n}{i}\rfloor)，我们发现在用杜教筛计算 G(n) 的过程中已经预处理了这些，直接使用即可。时间复杂度为杜教筛的 O(n^\frac23)。 例题：Min_25 模板 题意：积性函数 f 满足 f(p^k)=p^k(p^k-1)，求 \sum\limits_{i=1}^nf(i) 考虑如何使用杜教筛做 $G(n)$。 $$(g*\text{id})(n)=\sum\limits_{d|n}d\varphi(d)\dfrac{n}{d}=n\sum\limits_{d|n}\varphi(d)=n^2$$ 套用杜教筛公式，得到 $G(n)=\sum\limits_{i=1}^{n}i^2-\sum\limits_{i=2}^{n}i\cdot G(\lfloor\dfrac{n}{i}\rfloor) 接下来就是怎么做 h(p^c) 了。 \begin{aligned} &\qquad\quad f(p^c)=\sum\limits_{i=0}^cg(p^{c-i})h(p^i) \\ &\iff p^c(p^c-1)=\sum\limits_{i=0}^c p^{2c-2i-1}(p-1)h(p^i) \\ &\iff p^c(p^c-1)=h(p^c)+\sum\limits_{i=0}^{c-1} p^{2c-2i-1}(p-1)h(p^i) \\ &\iff h(p^c)=p^c(p^c-1)-\sum\limits_{i=0}^{c-1} p^{2c-2i-1}(p-1)h(p^i) \\ \end{aligned} 又有 h(p^{c-1})=p^{c-1}(p^{c-1}-1)-\sum\limits_{i=0}^{c-2} p^{2c-2i-3}(p-1)h(p^i) p^2h(p^{c-1})=p^{c+1}(p^{c-1}-1)-\sum\limits_{i=0}^{c-2} p^{2c-2i-1}(p-1)h(p^i) 上下二式相减，得到 \begin{aligned} &h(p^c)-p^2h(p^{c-1})=p^c(p^c-1)-p (p-1)h(p^{c-1})-p^{c+1}(p^{c-1}-1) \\ &\iff h(p^c)-ph(p^{c-1})=p^{c+1}-p^c \\ &\iff \dfrac{h(p^c)}{p^c}-\dfrac{h(p^c)}{p^c}=p-1 \\ &\iff \dfrac{h(p^c)}{p^c}=(p-1)(c-1) \\ &\iff h(p^c)=(p-1)(c-1)p^c \\ \end{aligned} 然后就做完了。 Min_25 筛 计算积性函数 f 的前缀和。f 需要满足： ### 记号 $\mathbb{P}$ 表示质数集合。 $lpf_i$ 表示 $i$ 的最小质因子。 $p_i$ 表示从小到大第 $i$ 个的质数。 ### 推导 以下推导中都不含有 $1$。 首先按照质数和合数分类。 对于合数的部分，枚举最小质因子进行拆分。 \sum\limits_{i=1}^nf_i=\sum\limits_{p=1,p\in \mathbb{P}}^nf(p)+\sum\limits_{p=1,p\in \mathbb{P}}^{\sqrt{n}}\sum\limits_{e=1}^{p^e \le n}f(p^e)(\sum\limits_{i=1,lpf_i>p}^{\frac{n}{p^e}}f(i)) 先考虑如何做质数的部分。可以将 f(i) 拆成多个完全积性函数之和。考虑完全积性函数 h(i) 的求和，构造 g_{n,i}，表示 1\sim n 中要么是质数，要么 lpf>p_i 的数的 h(i) 之和。从 g_{n,i-1} 转移到 g_{n,i} 的过程中我们需要减去 lcp=p_i 的数的贡献，即减去 h(p_i)(g_{\lfloor\frac{n}{p_i}\rfloor,i}-g_{p_{i-1},i-1})，后半部分是减去 g 中所有质数的贡献。 注意到 p_i \le \sqrt{n}，所以后半部分作为 p_{1\sim i-1} 的 k 次方之和，可以用线性筛预处理，时间复杂度 O(\sqrt{n})。记 sp_n=\sum\limits_{i=1,i\in \mathbb{P}}^{n}h(p_i)，那么转移方程为 g_{n,i}=g_{n,i-1}-h(p_i)(g_{\lfloor\frac{n}{p_i}\rfloor,i}-sp_{i-1}) 我们发现在全过程中只有 g_{\lfloor\frac{n}{i}\rfloor} 是有贡献的，所以只用处理出这一部分的 g 即可。在要求 p_i \le \sqrt{n} 的情况下，可以证明总状态数是 O(\frac{n^{\frac34}}{\log n}) 的，转移是 O(1) 的，所以时间复杂度为 O(\frac{n^{\frac34}}{\log n})。 最后将多个完全积性函数合并，即对多个 g 相加。下文中 g 指的是合并后的 g，即 g_{n,i} 表示 1\sim n 中要么是质数，要么 lpf>p_i 的数的 f 之和。同理 sp_n=\sum\limits_{i=1,i\in \mathbb{P}}^{n}f(i) 处理完质数部分，考虑合数部分如何处理。一样地，令 S_{n,i} 表示 lpf>p_i 的函数值之和。要求的即为 S_{n,0}。转移考虑一样地分离质数和合数： S_{n,i}=g_{n,+\infty}-sp_i+\sum_{p_k^e\le n,k>x}f(p_k^e)(S(\lfloor\frac{n}{p_k^e}\rfloor,k)+[e\not=1]) 解释：g_{n,+\infty} 表示所有小于等于 n 的质数的 f 之和，sp_i 表示 p_{1\sim i} 的 f 之和，二者的差表示大于 p_i 的所有质数的 f 之和。后半部分先枚举含有的最小质因子和次数，f(p_k^e)S(\lfloor\frac{n}{p_k^e}\rfloor,k) 表示所有 lpf=p_k 且质因数分解后 p_k 的次数为 e 的数的和。由于 S 中没有考虑 1 的贡献，所以对于所有的 e\not=1，即 p_k^e 不是质数的情况，需要单独加，所以有 [e\not=1] 一项。 至此，递归做 S 即可。同时我们发现我们只用求出 g_{\lfloor\frac{n}{i}\rfloor,j},p_j \le \sqrt{n} 的值即可，所以滚动数组。 过程 预处理数论分块结果。 递推计算 g。 递归得到 S。 模板题中 f(p)=p^2-p，p^2 和 p 都是完全积性函数，且 f(p^k) 容易求出。