线性筛合集

· · 个人记录

线性筛质数

inline void init(){
  for(int i=2;i<=n;++i){
    if(!isprime[i]){
      prime[++tot]=i;
    }
    for(int j=1;j<=tot&&prime[j]*i<=n;++j){
      isprime[prime[j]*i]=true;
      if(i%prime[j]==0) break;
    }
  }
}

这个板子还是背下来好吧。。（也很好理解）

欧拉函数

设 $n=p_1^{b_1}*p_2^{b_2}*p_3^{b_3}*·····*p_n^{b_n}

推论：（容斥定理）

\phi(n) = n(1-\frac{1}{p_1}-\frac{1}{p_2}-····+\frac{1}{p_1p_2}+\frac{1}{p_1p_3}+···+\frac{1}{p_{m-2}p_{m-1}}-\frac{1}{p_1p_2p_3}-···) \phi(n) = (1-\frac{1}{p_1}) * \phi(\frac{n}{p_1^{t_1}}) \phi(n) = n * \prod_{k}(1-\frac{1}{p_k}) \phi(n) = \prod_{k}(p_k-1)p_k^{t_k-1}

线性筛求欧拉函数

inline void init(){
  for(int i=2;i<=n;++i){
    if(!isprime[i]){
      prime[++tot]=i;
      phi[i]=i-1;
    }
    for(int j=1;j<=tot&&prime[j]*i<=n;++j){
      isprime[prime[j]*i]=true;
      phi[i*prime[j]]=i%prime[j]==0 ? phi[i]*prime[j] :phi[i]*(prime[j]-1);
      if(i%prime[j]==0) break;
    }
  }
}

线性筛求因数个数

设h (n) 为 n 的因子个数

引理：设 n = p_1^{t_1} * p_2 ^{t_2} * p_3^{t_3} *·····*p_n^{t_n}

h(n) = (t_1+1) * (t_2+1) * (t_3+1) * ··· * (t_n+1)

以上的 t_n 皆满足t_n<t_{n+1}

我们可以设两个数组 一个$gg_i$表示 $i$ 的最小质因数的指数+1 一个 $g_i$ 表示 $i$ 除了最小质因数其他所有质因数的指数+1的乘积 代码： ``` cpp inline void init(){ for(int i=2;i<=n;++i){ if(!isprime[i]){ prime[++tot]=i; g[i]=1; gg[i]=2; } for(int j=1;j<=tot&&prime[j]*i<=n;++j){ isprime[prime[j]*i]=true; gg[i*prime[j]]= i%prime[j]==0 ? gg[i]+1 : 2 ; g[i*prime[j]]= i%prime[j]==0 ? g[i] : g[i]*gg[i]; if(i%prime[j]==0) break; } } } ```