莫比乌斯函数

标签：函数 int 乌斯 mu 因子 莫比

唯一分解定理

\[n = \prod^{s}_{i=1} p_{i}^{a_i} = p_{1}^{a_1} p_{2}^{a_2} ··· p_{s}^{a_s} \]

莫比乌斯函数的定义

\[\mu (n) = \left\{ \begin{aligned} & 1 & & n = 1\\\ & 0 & & n含相同质因子\\\ & (-1)^s & & s为n的不同质因子的个数 \end{aligned} \right. \]

例：\(\mu \{ 1,6,10,15 \} = 1\), \(\mu \{ 4,8,9,12 \} = 0\), \(\mu \{ 2,3,5,7,30 \} = -1\)

筛法求莫比乌斯函数

若i是质数，\(\mu [i] = -1\)。

在线性筛中，每一个合数 \(m\) 都是被最最小的质因子筛掉的。

设\(p_j\)是 \(m\) 的最小质因子，则 \(m\) 通过 \(m = j \times p_j\) 筛掉

若 \(i\) 能被 \(p_j\) 整除，则 \(i\) 也包含质因子 。
\(\,\,\,\,\, \mu [m] = 0\)。
若 \(i\) 不能被 \(p_j\) 整除，则 \(m\) 比 \(i\) 多一个不同质因子 \(p_j\) 。
\(\,\,\,\,\,\)若 $\mu [i] = -1 $，则 \(\mu [m] = 1\) 。
\(\,\,\,\,\,\)若 $\mu [i] = 1 $，则 \(\mu [m] = -1\) 。
\(\,\,\,\,\,\)若 $\mu [i] = 0 $，则 \(\mu [m] = 0\) 。
\(\,\,\,\,\,\)所以 \(\mu [m] = - \mu [i]\)

const int N = 1000010;
int p[N], vis[N], cnt;
int mu[N];

void get_mu(int n){      //筛法求莫比乌斯函数
  mu[1] = 1;
  for(int i=2; i<=n; i++){
    if(!vis[i]){
      p[++cnt] = i;
      mu[i] = -1;
    }
    for(int j=1; i*p[j]<=n; j++){
      int m = i*p[j]; 
      vis[m] = 1;
      if(i%p[j] == 0){
        mu[m] = 0;
        break;
      } 
      else
        mu[m] = -mu[i];
    }
  }
}

标签：函数,int,乌斯,mu,因子,莫比
From： https://www.cnblogs.com/wqzgg/p/17094829.html