容斥原理

有\(n\)个集合\(S_n\)

莫比乌斯函数

对于正整数\(N\)，我们都可以将它进行唯一分解\(P_1^{c_1}P_2^{c_2}...P_k^{c_k}\)

我们就用\(\mu\)

注：\(\exists\)表示存在

用代码求

#include<iostream>
using namespace std;

void mobius(int n)
{
	for(int i = 1; i <= n; i++)
	{
		miu[i] = 1;
		vis[i]= false;
	}
	for(int i = 2; i <= n; i++)
	{
		if(vis[i] == true)
			continue;
		miu[i] = -1; //质数自己 ,-1
		for(int j = 2*i; j <= n; j+=i)
		{
			vis[j] = true;
			if(j % (i*i) == 0)
				miu[j] = 0;
			else
				miu[j] *= -1; //取相反数, j的质因数可能有多个，奇数个就是-1 
		} 
	}
	return ; 
}

int main()
{

	return 0;
}

容斥原理

原文：https://www.cnblogs.com/zhangwenxuan/p/14589897.html