[数论](9)容斥原理

容斥原理

例题:

思路(来自acwing的抽象带师佬):

伪码:

样例解释: 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中的倍数
//然后利用容斥原理求出答案

源码:

#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;
}

本文链接：