数学知识：容斥原理

前言

复习acwing算法基础课的内容，本篇为讲解数学知识：容斥原理，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。

一、容斥原理

其实类似于我们高中所接触过的韦恩图计算的方法，这里给出公式，具体的原因推导证明请面向百度：

二、AcWing 890. 能被整除的数

本题链接：AcWing 890. 能被整除的数
本博客提供本题截图：

本题解析

数组p存储的就是质数，记Si为在1~n中能整除p[i]的集合，我们根据容斥原理的公式，我们不需要知道每一个集合中的元素是什么，我们只需要知道每一个集合中的元素个数即可，故Si = n / p[i]，确定交集的数量，因为p[i]均为质数，这些质数的乘积就是他们的最小公倍数，n除这个最小公倍数就是交集的大小，那么如何知道一个集合的状态呢？即是否选取了这个集合：我们可以用二进制去表示，例如m = 5，那么对于01101就表示选择了S1,S3,S4，其余的解析详细见AC代码板块

AC代码

#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;const int N = 20;int p[N];int main()
{
    int n, m;cin >> n >> m;for (int i = 0; i < m; i ++ ) cin >> p[i];int res = 0;for (int i = 1; i < 1 << m; i ++ )   //每个集合都有选择或不选择的情况，所以总情况个数就是 1 << m - 1{
    int t = 1, s = 0;       //s代表有选择了多少个集合//t表示选中集合对应质数的乘积for (int j = 0; j < m; j ++ )  //遍历m个集合的选择情况if (i >> j & 1)  //如果有选择这个集合{
    if ((LL)t * p[j] > n)   //选择集合对应质数乘积超过了n{
     t = -1;break;}t *= p[j];              //计算乘积s ++ ;                  //选择的集合数 + 1}if (t != -1){
    if (s % 2) res += n / t;    //如果是奇数的话就加else res -= n / t;          //如果是偶数的话就减}}cout << res << endl;return 0;
}

三、时间复杂度

关于容斥原理各步操作的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。