常见积性函数线性筛

$\mu$函数
貌似根据定义做就可以。

void calmu(int n) {
    np[1] = true; mu[1] = 1;
    for(int i = 2; i <= n; i++) {
        if(!np[i]) prime[++pos] = i , mu[i] = -1;
        for(int j = 1; j <= pos && i * prime[j] <= n; j++) {
            np[i * prime[j]] = 1;
            if(i % prime[j]) {
                mu[i * prime[j]] = -mu[i];
            }
            else {
                mu[i * prime[j]] = 0;
                break;
            }
        }
    }
}

$\varphi$函数
考虑硬拆式子。
重温$\text{Euler Sieve}$的过程，就是找$n$的最小质因子$p_1$将其用$p_1 \times (n / p_1)$筛掉。
先设$n’ = n / p_1$，再分两种情况讨论：
$①:n’$有$p_1$这一因子。意味着唯一分解中$k_1 > 1$
那么显然，$n’$有着$n$的所有质因子。所以

$\begin{aligned} \varphi(n)&= n \prod\limits_{i = 1} ^ {k} \frac{p_i - 1}{p_i} \\ &= p_1 \times n' \prod\limits_{i = 1} ^ {k} \frac{p_i - 1}{p_i} \\ &= p_1 \times \varphi(n') \\ \end{aligned}$

$②:n’$没有$p_1$这一因子。意味着唯一分解中$k_1 = 1$

$\begin{aligned} \varphi(n)&= n \prod_{i = 1} ^ {k} \frac{p_i - 1}{p_i} \\ &= p_1 \times n' \times \frac{p_1-1}{p_1} \prod\limits_{i = 2} ^ {k} \frac{p_i - 1}{p_i} \\ &= (p_1-1) \times \varphi(n') \\ \end{aligned}$

（其实也证明了欧拉函数是积性函数）
愉快的筛就好了。注意任何积性函数都有$f(1) = 1$.

void Euler_Sieve(int x) {
  np[1] = 1; phi[1] = 1;
  Go(i , 2 , x) {
    if(!np[i]) prime[++cnt] = i , phi[i] = i - 1;
    for(int j = 1; j <= cnt && i * prime[j] <= x; j++) {
      np[i * prime[j]] = 1;
      if(i % prime[j])
        phi[i * prime[j]] = phi[i] * (prime[j] - 1);
      else  {
        phi[i * prime[j]] = prime[j] * phi[i];
        break;
      }
    }
  }
}

# 数论

常见积性函数线性筛

评论

分类

Your browser is out-of-date!