莫比乌斯反演是应用在有限偏序集上的容斥原理，什么是有限偏序集：令X是一个集合，X上的关系R是一个“性质”，在X的任意俩个给定的元素之间，这个性质可能成立也可能不成立。说的更正式一点，X上的关系是X×X的一个子集R，而X×X是X的元素的序偶集合。常见的偏序有：有一个集合含于另一个集合以及由一个整数被另一个整数。它们是在给定俩个集合互相都不是对方自己以及给定俩个整数彼此都不能整除意义下的偏序。

莫比乌斯反演：

• f(x) = sigma{g(d)}其中x % d == 0，则g(x) = sigma{miu(d) * f(x/d)}
• f(x) = sigma{g(d)}其中d % x == 0，则g(x) = sigma{miu(d/x) * f(d)}

莫比乌斯反演中miu(x) = 

• 1   {x中含有偶数个不同的质因子}
• -1  {x中含有奇数个不同的质因子}
• 0   {其他情况}

求miu(x)的代码：

const int maxn = 1001000;

int prime[maxn], miu[maxn], cnt;
bool check[maxn];

void Mobius() {
	memset(check, false, sizeof(check));
	cnt = 0; miu[1] = 1;
	for (int i = 2; i < maxn; i++) {
		if (!check[i]) {
			prime[cnt++] = i;
			miu[i] = -1;
		}
		for (int j = 0; j < cnt; j++) {
			if (i * prime[j] > maxn)
				break;
			check[i*prime[j]] = true;
			if (i % prime[j])
				miu[i*prime[j]] = 1;
			else {
				miu[i*prime[j]] == 0;
				break;
			}
		}
	}
}