容斥原理应用

样例解释

n = 10, $p_1 = 2, p_2 = 3$, 求1-10中能满足能整除$p_1$或$p_2$的个数, 即2，3，4，6，8，9，10,共7个

解题思路

记$S_i$为1-n 中能整除$p_i$的集合,那么根据容斥原理, 所有数的个数为各个集合的并集，计算公式如下 $$\bigcup_{i=1}^{m} S_i = S_1 + S_2 + \ldots + S_m - (S_1 \bigcap S_2 + S_1 \bigcap S_3 +\ldots + S_{m-1} \bigcap S_m) + (S_1 \bigcap S_2 \bigcap S_3 +\ldots + S_{m-2} \bigcap S_{m-1} \bigcap S_m) + \ldots + (-1)^{m - 1} (\bigcap_{i=1}^{m}S)$$

以题目样例为例
$S_1 = \lbrace 2,4,6,8,10 \rbrace , S_2 = \lbrace 3,6,9 \rbrace, S_1 \bigcap S_2 = \lbrace 6 \rbrace, 故S_1 \bigcup S_2 = \lbrace 2,3,4,6,8,9,10 \rbrace$

实现思路

1. 每个集合实际上并不需要知道具体元素是什么，只要知道这个集合的大小，大小为$|S_i| = n / p_i$, 比如题目中$|S_1| = 10 / 2 = 5, |S_2| = 10 / 3 = 3$

2. 交集的大小如何确定？因为$p_i$均为质数，这些质数的乘积就是他们的最小公倍数，n除这个最小公倍数就是交集的大小，故$|S_1 \bigcap S_2| = n / (p_1 \* p_2) = 10 / (2\*3) = 1$

3. 如何用代码表示每个集合的状态？这里使用的二进制，以m = 4为例，所以需要4个二进制位来表示每一个集合选中与不选的状态，$\overbrace{1 1 0 1}^{m = 4}$,这里表示选中集合$S_1, S_2, S_4$，故这个集合中元素的个数为 $n / (p_1 \* p_2 \* p_4)$, 因为集合个数是3个，根据公式，前面的系数为$(-1)^{3-1} = 1$。所以到当前这个状态时，应该是$res += n / (p_1 \* p_2 \* p_4)$ 。这样就可以表示的范围从$0000 到1111$的每一个状态

用二进制表示状态的小技巧非常常用，后面的状态压缩DP也用到了这个技巧，因此一定要掌握

AC代码

#include<iostream>
using namespace std;
typedef long long LL;

const int N = 20;
int p[N], n, m;

int main() {
    cin >> n >> m;
    for(int i = 0; i < m; i++) cin >> p[i];

    int res = 0;
    //枚举从1 到 1111...(m个1)的每一个集合状态, (至少选中一个集合)
    for(int i = 1; i < 1 << m; i++) {
        int t = 1;             //选中集合对应质数的乘积
        int s = 0;             //选中的集合数量

        //枚举当前状态的每一位
        for(int j = 0; j < m; j++){
            //选中一个集合
            if(i >> j & 1){
                //乘积大于n, 则n/t = 0, 跳出这轮循环
                if((LL)t * p[j] > n){    
                    t = -1;
                    break;
                }
                s++;                  //有一个1，集合数量+1
                t *= p[j];
            }
        }

        if(t == -1) continue;  

        if(s & 1) res += n / t;              //选中奇数个集合, 则系数应该是1, n/t为当前这种状态的集合数量
        else res -= n / t;                      //反之则为 -1
    }

    cout << res << endl;
    return 0;
}