[数论](9)容斥原理
容斥原理
例题:
思路(来自acwing的抽象带师佬):
伪码:
```C++ 样例解释: n = 10, p1=2,p2=3,求1-10中能满足能整除p1或p2的个数, 即2,3,4,6,8,9,10,共7个 S1={2,4,6,8,10},S2={3,6,9},S1 ⋂ S2={6},故S1 ⋃ S2={2,3,4,6,8,9,10} //先求出能每个质数在1-n中的倍数 //然后利用容斥原理求出答案
源码:
```C++
#include<iostream>
using namespace std;
int n,m,prime[17];
int main(){
cin>>n>>m;
for(int i=0;i<m;i++)
cin>>prime[i];
int res=0;
//枚举从1到1111...(m个1)的每一个集合状态,(至少选中一个集合)
for(int i=1;i<1<<m;i++){
int cnt=0,t=1;//cnt为选中的集合数量,t为选中集合对应质数的乘积
//枚举当前状态的每一位
for(int j=0;j<m;j++){
//选中一个集合
if(i>>j&1){
//若乘积大于n,则n/t为0,跳过这轮循环
if((long long)t*prime[j]>n){
t=-1;
break;
}
cnt++;//有一个1,集合数量+1
t*=prime[j];
}
}
if(t==-1) continue;
if(cnt%2) res+=n/t;//选中奇数个集合,则系数应该是1,n/t为当前这种状态的集合数量
else res-=n/t;//反之则为-1
}
cout<<res<<endl;
return 0;
}