[笔记] 线性筛小记

本文讲了

  1. 线性筛质数
  2. 线性筛$\varphi(n)$
  3. 线性筛$\mu(n)$
  4. 线性筛$d(n)$(因数个数)
  5. 线性筛$\sigma(n)$(约数和)

 

一、线性筛质数

  • 就扔个代码吧,具体详见欧拉线性筛 和 欧拉函数的求值
    inline void PRI(int n) {
        for(R i=2;i<=n;++i) {
            if(!v[i]) pri[++cnt]=i;
            for(R j=1;j<=cnt&&i*pri[j]<=n;++j) {
                v[i*pri[j]]=true; if(i%pri[j]==0) break;
            }
        }
    }

二、线性筛$\varphi(n)$

  • 也详见欧拉线性筛 和 欧拉函数的求值
    inline void PHI(int n) { p[1]=1;
        for(R i=2;i<=n;++i) {
            if(!v[i]) pri[++cnt]=i,p[i]=i-1;
            for(R j=1;j<=cnt&&i*pri[j]<=n;++j) {
                v[i*pri[j]]=true; 
                if(i%pri[j]==0) {p[i*pri[j]]=p[i]*pri[j]; break;}
                p[i*pri[j]]=p[i]*p[pri[j]];
            }
        }
    }

三、线性筛$\mu(n)$

  • $\mu(n)=\begin{cases} 0&有平方素因子  \\ 1&素因子个数为偶数\\ -1&素因子个数为奇数\end{cases}$
  • 直接根据定义去筛
    inline void MU(int n) { mu[1]=1;
        for(R i=2;i<=n;++i) {
            if(!v[i]) pri[++cnt]=i,mu[i]=-1;
            for(R j=1;j<=cnt&&i*pri[j]<=n;++j) {
                v[i*pri[j]]=true;
                if(i%pri[j]==0) break;
                mu[i*pri[j]]=-mu[i];
            }
        } 
    }

     

四、线性筛$d(n)$(因数个数)

  • 首先公式:$n=\prod_{i=1}^k\space p_i^{c_i}$,那么$d(n)=\prod_{i=1}^k\space (c_i+1)$
  • 记$d[n]$为$n$的因数个数,$c[n]$为$n$最小素因子出现次数;
    inline void D(int n) { d[1]=1;
        for(R i=2;i<=n;++i) {
            if(!v[i]) pri[++cnt]=i,d[i]=2,c[i]=1;
            for(R j=1;j<=cnt&&i*pri[j]<=n;++j) {
                v[i*pri[j]]=true;
                if(i%pri[j]==0) {
                    c[i*pri[j]]=c[i]+1;
                    d[i*pri[j]]=d[i]/(c[i]+1)*(c[i]+2);
                    break;
                } d[i*pri[j]]=d[i]*2;
                c[i*pri[j]]=1;
            }
        }
    }
  • 若$i$是素数,则显然$d[i]=2,c[i]=1$
  • 若$i$不是素数,则要分类讨论
  1. 若$i%pri[j]==0$,说明$pri[j]$是$i$的最小素因子(因为素数是从小到大枚举的),所以$c[i*pri[j]]=c[i]+1$,而$d[i]=(c[i]+1)*(k_1+1)*(k_2+1)*...$,所以此时$c[i*pri[j]]$比$c[i]$增大了$1$,所以$d[i*pri[j]]=d[i]/(c[i]+1)*(c[i]+2)$
  2. 若$i%pri[j]!=0$,说明$pri[j]$是$i*pri[j]$的最小素因子,所以$c[i*pri[j]]=1$,对于$i$来说,相当于添了一个以前没有的素因子$pri[j]$,所以$d[i*pri[j]]=d[i]*2$.

五、线性筛$\sigma(n)$(约数和)

  • 首先公式:$n=\prod_{i=1}^k\space p_i^{c_i}$,那么$\sigma(n)=\prod_{i=1}^k 1+p_i+p_i^2+...+p_i^{c_i}=\prod_{i=1}^k\sum_{j=0}^{c_i} p_i^j$
  • 记$s[n]$为$n$的因数和,$c[n]$为$1+p_{min}+p_{min}^2+...+p_{min}^c$,其中$p_{min}$表示的是$n$的最小素因子,$c$是最小素因子在$n$中的的出现次数。
    inline void SIGMA() { s[1]=1;
        for(R i=2;i<=n;++i) {
            if(!v[i]) pri[++cnt]=i,s[i]=i+1,c[i]=i+1;
            for(R j=1;j<=cnt&&i*pri[j]<=n;++j) {
                v[i*pri[j]]=true;
                if(i%pri[j]==0) {
                    c[i*pri[j]]=c[i]*pri[j]+1;
                    s[i*pri[j]]=s[i]/c[i]*c[i*pri[j]];
                    break;
                } c[i*pri[j]]=pri[j]+1;
                s[i*pri[j]]=s[i]*(pri[j]+1);
            }
        }
    }
  • 若$i$是素数,则显然$s[i]=i+1,c[i]=i+1$
  • 若$i$不是素数,则又要分类讨论
  1. 若$i%pri[j]==0$,说明$pri[j]$是$i$的最小素因子(因为素数是从小到大枚举的),所以原来的$\\1+p_{min}+p_{min}^2+...+p_{min}^c\\$,要变成$\\1+p_{min}+p_{min}^2+...+p_{min}^{c+1}\\$,所以在原来的基础上乘上$p$,再加个$1$就好了,所以$c[i*pri[j]]=c[i]*pri[j]+1$,而$d[i]=(c[i]+1)*(c_1+1)*(c_2+1)*...$,所以此时,$s[i*pri[j]]$也相应转化就好了。
  2. 若$i%pri[j]!=0$,说明$pri[j]$是$i*pri[j]$的最小素因子,所以$c[i*pri[j]]=pri[j]+1$,对于$i$来说,相当于添了一个以前没有的素因子$pri[j]$,所以$s[i*pri[j]]=s[i]*(pri[j]+1)$.

如果觉得我的四和五讲得不太清楚,安利一发大佬的博客


 

2019.06.08

上一篇:c – 没有union的hashcode的内存地址


下一篇:加密和签名的区别