文章目录
前言
一、容斥原理
二、AcWing 890. 能被整除的数
本题解析
AC代码
三、时间复杂度
前言
复习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; }
三、时间复杂度
关于容斥原理各步操作的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
