|
画韦恩图
原理：S=s1+s2+s3-s1^s2-s2^s3-s1^s3+s1^s2^s3
推广：S=s1+s2+s3+s4-s1^s2-s2^s3-s1^s3-s1^s4-s2^s4-s3^s4+s1^s2^s3+s1^s2^s4+s2^s3^s4-s1^s2^s3^s4；n个同理
口诀:奇加偶减
时间复杂度：2^n
选法集合个数：2^n-1;
例题：能被整除的数
分析
#include
#include
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 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 ++ ;
}
}
// 再将提取出的取法代入公式-
// 如果t不等于-1（-1是给定的flag值）
if (t != -1)
{
// ③ s为什么要模2?
if (s % 2) res += n / t;
else res -= n / t;
}
}
cout |