题目描述
容斥原理
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,m;
int primes[20];
//容斥原理:集合的并等于集合的交的交错和(奇正偶负)
//能被p1整除的数共n/p1个,能被p1,p2同时整除的数的个数有n/(p1*p2)个...
//共有2^m个状态(每个状态只有取或不取某个质数),可以用0~2^m-1之间的二进制数表示其中的每一个状态
//至少能被其中一个质数整除即对应了所有质数集合的并集
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++) cin>>primes[i];
int res=0;
for(int i=1;i<(1<<m);i++)
{
ll t=1;
int sign=-1;
for(int j=0;j<m;j++)
{
if(i&(1<<j))//考虑了该质数
{
if(t*primes[j]>n)//注意t可能会爆long long,故超过n时就退出即可
{
t=0;
break;
}
t*=primes[j];
sign*=-1;
}
}
if(t) res+=n/t*sign;
}
cout<<res;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla