转自：http://blog.csdn.net/f_zyj/article/details/51852672

莫比乌斯反演公式

则 

莫比乌斯函数µ 

另一种更常用的形式： 
在某一个范围内： 则 

线性筛法求解

/**  莫比乌斯反演公式*  线性筛法求解积性函数（莫比乌斯函数）*/
const int MAXN = 1000000;
bool check[MAXN + 10];
int prime[MAXN + 10];
int mu[MAXN + 10];void Moblus()
{memset(check, false, sizeof(check));mu[1] = 1;int tot = 0;for (int i = 2; i <= MAXN; i++){if (!check[i]){prime[tot++] = i;mu[i] = -1;}for (int j = 0; j < tot; j++){if (i * prime[j] > MAXN){break;}check[i * prime[j]] = true;if (i % prime[j] == 0){mu[i * prime[j]] = 0;break;}else{mu[i * prime[j]] = -mu[i];}}}
}

单独求解

int MOD(int a, int b)//求余
{return a - a / b * b;
}int miu(int n)
{int cnt, k = 0;for (int i = 2; i * i <= n; i++){if (MOD(n, i)){continue;}cnt = 0;k++;while (MOD(n, i) == 0){n /= i;cnt++;}if (cnt >= 2){return 0;}}if (n != 1){k++;}return MOD(k, 2) ? -1 : 1;
}