莫比乌斯函数

定义

求法

方法1. 直接暴力分解质因数

太水了。

方法2. 埃氏筛

\(O(n\log\log n)\)

方法3. 线性筛

for(int i = 2;i<=n;i++){
	if(!is_prime[i]){
		prime[++cnt] = i;
		mu[i] = -1;
	}
	for(int j = 1;j<=cnt&&i*prime[j]<=n;j++){
		is_prime[i*prime[j]] = 1;
		if(i%prime[j]==0){
			mu[i*prime[j]] = 0;
			break;
		}else{
			mu[i*prime[j]]*=-1;
		}
	}
}