筛法求莫比乌斯函数

根据整数惟一分解定理

$\forall n\in\mathbb{N},,n>1\quad\exist \prod_{i=1}^s p_i^{a_i}=n$

同样莫比乌斯为积性函数

2023-12-05_13-15-39

μ{1,6,10,15} = 1 , μ{4,8,9,12} = 0 , μ{2,3,5,7,30} = -1

若$i$为质数只有两个因子所以 -1

若$i$ 为合数 $m = i \times pj$

若$m$是被最小质因子$pj$ 筛掉，那$pj$也一定是$i$的最小质因子，说明$m$含有相同的质因子

∴$mu[m] = 0$

若$i$不能被$pj$整除说明 $pj$为$m$的新的质因子 , $m$比$i$多一个质因子,为函数的第三段反转以下即可

∴$mu[m] = -mu[i]$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


const int N = 1919810;
int p[N];
int mu[N];
bool vis[N];
int cnt = 0;
void gen(){
    for(int i = 2;i<=114514;++i){
        if(!vis[i]){
            p[++cnt] = i;
            mu[i] = -1;
        }
        for(ll j = 1;i*1ll*p[j]<=114514;++j){
            int m = i*1ll*p[j];
            vis[m] = true;
            if(i % p[j] == 0){
                mu[m] = 0;
                break;
            }else{
                mu[m] = -mu[i];
            }
        }
    }
}