1. 题目
2. 读题(需要重点注意的东西)
思路:
容斥原理:
本题思路:
本题的思路其实就是代公式,为了代入公式我们要分别解决如下三个问题:
① 求出每个集合中元素的个数
② 求出集合和集合之间交集的个数
③ 用二进制表示选择了哪个集合与否
代码实现思路:
1、每一个i代表一种可能的取法,最外层的循环遍历置2的m次方后,可以取完所有的取法
2、里面的循环就是提取出这个i值对应的取法
3、再将提取出的取法代入公式
3. 解法
---------------------------------------------------解法---------------------------------------------------
#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;
// 用p数组存储m个质数
for (int i = 0; i < m; i ++ ) cin >> p[i];
int res = 0;
// --------------------1、每一个i代表一种可能的取法,最外层的循环遍历置2的m次方后,可以取完所有的取法--------------------
// ① 为什么是2的m次方?最外层循环的作用是什么?
// 从1开始枚举,枚举到1 << m(左移m位。左移一位相当于乘2,右移一位相当于除2),即2的m次方;
for (int i = 1; i < 1 << m ; i ++ )
{
// t代表当前所有质数的乘积,s代表什么当前选法包含几个集合
int t = 1, s = 0;
// --------------------2、这个循环就是提取出这个i值对应的取法--------------------
// 枚举m个质数,依次计算容斥原理的公式
for (int j = 0; j < m; j ++ ){
// i右移j位与上1,即如果当前位是1的话
// ② i在这里为什么要用位运算?
if (i >> j & 1)
{
// (LL)t * p[j] > n
// 如果t(已有的质数选法)乘上这个质数大于给定的数n,说明1∼n中的数不能被p整除
// 此时直接返回break,跳过这个质数
if ((LL)t * p[j] > n)
{
t = -1;
break; // break的作用域是跳出整个循环
}
// 将该质数乘到t中
t *= p[j];
// s表示当前选法中有多少个集合
s ++ ;
}
}
// --------------------3、再将提取出的取法代入公式--------------------
// 如果t不等于-1(-1是给定的flag值)
if (t != -1)
{
// ③ s为什么要模2?
if (s % 2) res += n / t;
else res -= n / t;
}
}
cout << res << endl;
return 0;
}
可能存在的问题
① 最外层循环的作用是什么?为什么是2的m次方?
for (int i = 1; i < 1 << m ; i ++ )
解答:
这个是用位运算来作枚举,从1枚举到2的m次方减1
把i看做一个二进制数,如i = 5(十进制下)= 00101(二进制下),表示p1、p3被选了
最外层的循环的作用是枚举从1到2的m次方减1的数,然后求出每个数的能被 p1,p2,…,pm 中的数整除的个数
② 循环中 i 为什么要做位运算?
if (i >> j & 1)
解答:
这里是为了求出哪一位上是1,从而计算出1对应的位置的集合的交集数
③ s为什么要模2?
if (t != -1)
{
// ③ s为什么要模2??
if (s % 2) res += n / t;
else res -= n / t;
}
解答:
根据容斥原理公式,这里其实是模拟(-1)^n-1
奇数个集合是加,偶数个集合是减
4. 可能有帮助的前置习题
5. 所用到的数据结构与算法思想
- 容斥原理
6. 总结
求组合数第五种题型(卡特兰数)的模板题,理解卡特兰数的思想并背下代码。
Orz
十分的感谢博主
orz%%%
字真好看
nb懂了
解释的真好
太强了
写的真棒!
谢谢~hhh
写的很棒。看到你这个才弄懂。点赞
牛逼…