线性筛莫比乌斯函数

模拟赛中的一道题，让我发现自己莫比乌斯函数的基础十分薄弱。😢

推导

先来看看莫比乌斯函数的定义：

设 $n=\prod_{i=1}^Np_i^{k_i}$（$p$ 为质数集合），则

$\mu(n)= \begin{cases} 1&n=1\\ (-1)^N&\forall1\leq i\leq N,k_i=1\\ 0&k_i>1 \end{cases}$

当 $i\in p$ 时，显然 $\mu(i)=-1$。

设 $n^\prime=\frac n{p_1}$，在线性筛中，$n$ 通过 $n^\prime\cdot p_1$ 被筛去。

当 $n^\prime\mid p_1$，即 $k_1>1$ 时，$\mu(n)=0$；

否则 $n^\prime$ 有 $N-1$ 个质因子。

如果 $\mu(n^\prime)\neq0$，即 $\forall2\leq i\leq N,k_i=1$ 时，根据定义得：

$\begin{aligned}\mu(n)&=(-1)^N\\&=(-1)^{N-1}\cdot(-1)\\&=\mu(n^\prime)\cdot(-1)\\&=-\mu(n^\prime)\end{aligned}$

如果 $\mu(n^\prime)=0$，则 $n^\prime$ 一定有次数大于 $1$ 的质因子，所以 $n$ 也一定有，即 $\mu(n)=0$。

此时 $\mu(n)=-\mu(n^\prime)$ 仍成立。

代码

mu[1]=1;
for(int i=2;i<=N;++i) {
    if(!npri[i]) {
        pri[++cnt]=i;
        mu[i]=-1;
    }
    for(int j=1,tem;(j<=cnt)&&((tem=i*pri[j])<=N);++j) {
        npri[tem]=true;
        if(i%pri[j]==0) {
        break;
    }
        mu[tem]=-mu[i];
    }
}

资料

本文部分参考线性筛法筛素数、莫比乌斯函数、欧拉函数 | Menci’s Blog。