## 容斥定理 要计算几个集合并集的大小，我们要先将所有单个集合的大 小计算出来，然后减去所有两个集合相交的部分，再加回所有三个集合相交的部分，再减去所有四个集合相交的部分， 依此类推，一直计算到所有集合相交的部分。 用Venn图来表示  数学公式描述  如果要对n个物体进行选择，那么有多少种情况？ 代码 复杂度为O(2^n) ~~~ for(int i=0;i<(1 << m);i++){    for(int j=0;j<n;j++){        printf("%d",i>>j & 1);   }    puts(""); } ~~~ #### 容斥定理的应用 问题：魔镜给小明m个数字（a1、a2 …… am）和一个整数n，魔镜定义：如果有一个数，是这m个数字里面任意一 个数的倍数，那么这个数称为LuckyNumber。而小明会的题 数为\[1,n\]闭区间内LuckyNumber的数量。 (0 < m < 15) 那么请你帮小明计算一下他会的题目数。 代码 复杂度为O(2^n) ~~~ LL ans=0; for(int i=1; i<(i<<m);i++){    int cnt=0;    LL LCM=1;    for(int j=0;j<m;j++){        if(1&(i>>j)){//按位运算判断第m个数是否使用            cnt++;            LCM=lcm(LCM,a[j]);       }   }    if(cnt&1) ans+=n/LCM;//判断n中元素使用的个数，奇加偶减    else ans-=n/LCM; } ​ printf("%lld\n",ans); ~~~