筛法求莫比乌斯函数

唯一分解定理： $n~=~\prod_{i=1}^{s}p_{i}{}^{\alpha_{i}}\,=\,p_{1}{}^{\alpha_{1}}p_{2}{}^{\alpha_{2}}\cdots p_{s}{}^{\alpha_{s}}$ 莫比乌斯函数定义： $\mu(n)=\left\{\begin{array}{ll} 1 & n=1 \\ 0 & n \text { 含相同质因子 } \\ (-1)^{s} & s \text { 为 } n \text { 的不同质因子的个数 } \end{array}\right.$ 例如：$\mu[1,6,10,15]=1,\mu[4,8,9,12]=0,\mu[2,3,5,7,30]=-1$ 筛法求莫比乌斯函数： 若i是质数，$\mu[i]=-1$,在线性筛中，每个合数被最小质因子筛去，设$p_i$是$m$的最小质因子，则$m$通过$i*p_i$筛掉。

1. 如果$i$能被$p_i$整除，则$i$也包含质因子$p_i$,此时$\mu(m)=0$
2. 如果$i$不能被$p_i$整除，则$m$比$i$多一个不同的质因子$p_i$,此时$\mu(m)=-\mu(m)$,原因如下：
   1. 如果$\mu(i)=-1$,则$\mu(m)=1$
   2. 如果$\mu(i)=0$,则$\mu(m)=0$
   3. 如果$\mu(i)=1$,则$\mu(m)=-1$

代码：

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define debug(x) cout<<"a["<<x<<"]="<<a[x]<<endl;
#define pr(x) cout<<x<<endl;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;

int p[N], st[N], cnt;
int mu[N];

//筛法求莫比乌斯函数
void get(int n) {
    mu[1]=1;
    for(int i=2;i<=n;i++){
        if (!st[i]){//质数
            p[++cnt]=i;//加入到质数中去
            mu[i]=-1;//第一次筛到肯定为-1
        }
        for(int j=1;i*p[j]<=n;j++){
            st[i*p[j]]=true;
            if (i%p[j]==0){
                mu[i*p[j]]=0;//i*p[j]至少有两个质因子
                break;
            }else{
                mu[i]=-mu[i];
            }
        }
    }

}

int main() {
    IOS;
#ifndef ONLINE_JUDGE
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.in", "r", stdin);
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.out", "w", stdout);
#endif
    int n;
    cin >> n;
    get(n);
    for (int i = 1; i <= n; i++)
        pr(mu[i])

    return 0;
}