线性筛

线性筛

闲话

之前写的总结不忍直视(总结了个寂寞),今天突然要用到约数和结果不会筛,于是爬来写博客。

性质

  • 时间复杂度线性
  • 理论上所有积性函数都可以筛(推式子)

用法

对于需要筛的积性函数,我们需要讨论三种数时它的取值或者转移。

  1. 当 \(i\) 为素数时,此时函数的值一般可以快速得到;
  2. 当 \(i\mod p=0\) 时;
  3. 当 \(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\) 来表示该数的最小素因子的数量,以便进行第二条转移。

  1. \(g_i=1,d_i=2\)。
  2. 此时枚举数 \(i\) 的最小约数已经之前被更新过了并且一定是当前正在枚举的 \(p\) ,则 \(g_{tmp}=g_i+1\)。对于 \(d_{tmp}\),根据上述公式,那我们就从 \(d_i\) 进行转移,更新最小约数的贡献,即除掉更改的贡献乘上正确的,即 \(d_{tmp}=d_i*\frac{g_{tmp}+1}{g_i+1}\)。
  3. 此时枚举的 \(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\)。

  1. \(g_i=\sigma_i=i+1\)
  2. 根据 \(g\) 的定义,我们要更新 \(g\) 就相当于给原来的 \(g\) 乘上 \(p\) 并加 1。对于 \(\sigma\),和上面的转移类似,我们从 \(i\) 转移即可。\(\sigma_{tmp}=\sigma_i*\frac{g_{tmp}}{g_i}\)。
  3. 此时我们计算上一个新的质数的贡献即可,和上面类似。

代码中 \(\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]];
	}
}

总结

如果要使用线性筛来筛积性函数,大多要表示成枚举所有质因数来统计贡献的形式才可以推出式子。更多技巧待耕。

上一篇:PE639 Summing a multiplicative function


下一篇:利用select语句对列进行过滤检索