数论函数学习笔记之线性筛

其实主要是想发一下线性筛的板子，包括线性筛质数，欧拉函数和莫比乌斯函数。
当然也会有一点简单的证明。


线性筛质数就不说啦。


然后加一个筛欧拉函数。
当\(i\)为质数的时候，自然\(\varphi(i) = i - 1\)。
令\(n = mp\)，
当\(m \ \ mod \ \ p == 0\)的时候，有\(\varphi(n) = \varphi(m) * p\)。
否则有\(\varphi(n) = \varphi(m) * (p - 1)\)。


证明一下吧：
1.若\(m \ \ mod \ \ p == 0\)，令\(m = k * p ^ x\)，这样保证了\(k, p\)互质。
所以
\(\varphi(n) = \varphi(k) * \varphi(p ^ {x + 1})\)
???\(= \varphi(k) * p ^ x * (p - 1)\)


然后看等式右边：
\(\varphi(m) * p = \varphi(k) * \varphi(p ^ x) * p\)
??????$ = \varphi(k) * p ^ {x - 1} * (p - 1) * p$
??????$ = \varphi(k) * p ^ x * (p - 1)$
（也不知道这算不算证明）


至于\(m \ \ mod \ \ p \neq 0\)时，根据积性，\(\varphi(n) = \varphi(m) * (p - 1)\)。


至于筛莫比乌斯函数，就更简单了。
如果\(n\)为质数，则\(\mu(n) = -1\)。
若\(m \ \ mod \ \ p == 0\)，则\(\mu(n) = 0\),
否则\(\mu(n) = - \mu(m)\)。

void init()
{
  phi[1] = mu[1] = 1;
  for(int i = 2; i <= n; ++i)
    {
      if(!v[i]) v[i] = i, prime[++prime[0]] = i, phi[i] = i - 1, mu[i] = -1;
      for(int j = 1; i * prime[j] <= n && j <= prime[0]; ++j)
    {
      int k = i * prime[j];
      v[k] = prime[j];
      if(i % prime[j] == 0)
        {
          phi[k] = prime[j] * phi[i];
          mu[k] = 0;
          break;
        }
      else phi[k] = (prime[j] - 1) * phi[i], mu[k] = -mu[i];
    }
    }
}

数论函数学习笔记之线性筛

原文：https://www.cnblogs.com/mrclr/p/10106609.html