定义
在计数时，必须注意没有重复，没有遗漏
为了使重叠部分不被重复计算，人们研究出一种新的计数方法
这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复
这种计数的方法称为容斥原理
想必大家都不想读这么多字，而且读了还不一定懂
所以我们用维恩图来看一下：
简单明了，其实容斥原理就是小学学的重叠问题
公式
在百度百科中所展现的式子是这样的
而对于像我这样的初学者来看无疑是“天书”
所以我总结了一个式子
公式含义
如图，当我们减去两两相交的部分时，三个部分都重合的那个被减去了三次
因此需要加上一次
其实容斥也就这么多了
作为Oier，我们还要会敲代码
模板题 HDU Eddy’s爱好
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int prime[18]= {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59};
LL res, n;
int a[5];
void dfs(int cur, int num, int cnt, LL sum) { // 从素数表cur位置开始，当前一共num个，需要cnt个，当前素数乘积为sum
if (num == cnt) {
LL temp = (LL) pow(n + 0.5, 1.0 / sum);
if (temp > 1) res += temp - 1; // 减去1的情况
return;
}
for (int i = cur; i < 17; i++) {
if (sum * prime[i] < 60) dfs(i + 1, num + 1, cnt, sum * prime[i]);//如果素数没到60，则这个素数可以取
else dfs(i + 1, num, cnt, sum);// 否则跳过该数
}
}
int main() {
while (scanf("%d", &n) != EOF) {
LL sum = 0;
for (int i = 1; i <= 3; i++) {
res = 0;
dfs(0, 0, i, 1);
if (i & 1) sum += res;
else sum -= res;
}
printf("%d\n", sum + 1);
}
return 0;
}
