容斥原理

佚名 6年前 (2019-04-09) 随笔 1207人围观抢沙发百度已收录

容斥原理

定义

在计数时，必须注意没有重复，没有遗漏
为了使重叠部分不被重复计算，人们研究出一种新的计数方法
这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复
这种计数的方法称为容斥原理

想必大家都不想读这么多字，而且读了还不一定懂
所以我们用维恩图来看一下：

简单明了，其实容斥原理就是小学学的重叠问题

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

公式

在百度百科中所展现的式子是这样的

而对于像我这样的初学者来看无疑是“天书”
所以我总结了一个式子

公式含义

如图，当我们减去两两相交的部分时，三个部分都重合的那个被减去了三次
因此需要加上一次
其实容斥也就这么多了
作为Oier，当然我们还要会敲代码
找了一道模板题

HDU Eddy's爱好
代码：

#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;
}