线性筛
闲话
之前写的总结不忍直视(总结了个寂寞),今天突然要用到约数和结果不会筛,于是爬来写博客。
性质
- 时间复杂度线性
- 理论上所有积性函数都可以筛(推式子)
用法
对于需要筛的积性函数,我们需要讨论三种数时它的取值或者转移。
- 当 \(i\) 为素数时,此时函数的值一般可以快速得到;
- 当 \(i\mod p=0\) 时;
- 当 \(i\mod p\ne 0\) 时。
对于不同数论函数当然每处的转移都不同了。
下文所有标号位置对应以上三种情况,并设 \(tmp=i*p\)
例子
约数个数和
根据算术基本定理(?),设数 \(n\) 的约数个数和为 \(d_n\),有:
\[n=\prod_{p_i\mid n \and p_i\mathrm{\ is\ a\ prime}}p_i^{g_i}\\ d_n=\prod g_i+1 \]要筛 \(d\) 我们还需要一个 \(g\) 来表示该数的最小素因子的数量,以便进行第二条转移。
- \(g_i=1,d_i=2\)。
- 此时枚举数 \(i\) 的最小约数已经之前被更新过了并且一定是当前正在枚举的 \(p\) ,则 \(g_{tmp}=g_i+1\)。对于 \(d_{tmp}\),根据上述公式,那我们就从 \(d_i\) 进行转移,更新最小约数的贡献,即除掉更改的贡献乘上正确的,即 \(d_{tmp}=d_i*\frac{g_{tmp}+1}{g_i+1}\)。
- 此时枚举的 \(p\) 是最小的素因子,那么根据公式,\(g_{tmp}=1,d_{tmp}=d_i*2\)。
d[1]=1;
for(int i=2;i<=n;i++){
if(!mark[i]) p[++tot]=i,d[i]=2,g[i]=1;
for(int j=1,tmp;j<=tot and (tmp=i*p[j])<=n;j++){
mark[tmp]=true;
if(i%p[j]==0){
g[tmp]=g[i]+1;
d[tmp]=d[i]/(g[i]+1)*(g[tmp]+1);
break;
}
g[tmp]=1;
d[tmp]=d[i]*[g[tmp]+1];
}
}
约数和
根据算术基本定理(?),已知 \(\sigma\) 为约数和,有:
\[\sigma_n=\prod_{p_i\mid n\and p_i\mathrm{\ is\ a\ prime}}\sum_{j=0}^{a_i}p_i^j \]注意这里的 \(a\) 与上文的 \(g\) 表示意义相同,为每个素数的个数。我们定义 \(g\) 为最小的 \(p\) 的 \(\sum_{j=0}p^j\)。
- \(g_i=\sigma_i=i+1\)
- 根据 \(g\) 的定义,我们要更新 \(g\) 就相当于给原来的 \(g\) 乘上 \(p\) 并加 1。对于 \(\sigma\),和上面的转移类似,我们从 \(i\) 转移即可。\(\sigma_{tmp}=\sigma_i*\frac{g_{tmp}}{g_i}\)。
- 此时我们计算上一个新的质数的贡献即可,和上面类似。
代码中 \(\sigma\) 用 \(f\) 代替。
f[1]=1;
for(int i=2;i<=n;i++){
if(!mark[i]) p[++tot]=i,g[i]=f[i]=i+1;
for(int j=1,tmp;j<=tot and (tmp=i*p[j])<=n;j++){
mark[tmp]=true;
if(i%p[j]==0){
g[tmp]=g[i]*p[j]+1;
f[tmp]=f[i]/g[i]*g[tmp];
break;
}
g[tmp]=p[j]+1;
f[tmp]=f[i]*f[p[j]];
}
}
总结
如果要使用线性筛来筛积性函数,大多要表示成枚举所有质因数来统计贡献的形式才可以推出式子。更多技巧待耕。