容斥原理

$$ 假设我们需要求集合s_1,s_2,s_3,\dots,s_n的集合元素个数|s_1\cup s_2\dots\cup s_n| $$

$$ = |s_1|+|s_2|+\dots+|s_n|-|s_1|\cap |s_2|-|s_1\cap s_3|-\dots+|s_1\cap s_2\cap s_3|+|s_1\cap s_2\cap s_4|+\dots-\dots $$

$$ 可用数学归纳法对容斥原理进行严格证明 $$

$$ 时间复杂度O(2^n) $$

AcWing 890. 能被整除的数 原题链接

给定一个整数nn和mm个不同的质数p1,p2,…,pmp1,p2,…,pm。

请你求出11~nn中能被p1,p2,…,pmp1,p2,…,pm中的至少一个数整除的整数有多少个。

输入格式

第一行包含整数nn和mm。

第二行包含mm个质数。

输出格式

输出一个整数，表示满足条件的整数的个数。

数据范围

1≤m≤161≤m≤16,
1≤n,pi≤1091≤n,pi≤109

输入样例：

10 2
2 3

输出样例：

7

题目思路

$$ 将能整除p_i的集合表示为sp_i则|sp_1\cup sp_2\dots\cup\ sp_m|可用容斥原理表示 $$

$$ 我们可以用二进制来枚举所有的选法，选出的集合为奇数符号是正的，偶数符号是负的 $$

$$ 并且在[1,n]中，p_1p_2\dots p_i(1<=i<=m)的倍数的个数为\lfloor\frac{n}{p_ip_2\dots p_i}\rfloor $$

    public static void main(String[] args) {
        int n = in.nextInt();
        int m = in.nextInt();
        int[] p = new int[m];
        in.nextIntegerArray(p);
        long res = 0L;
        for (int i = 1; i < 1 << m; i++) {
            long t = 1L;
            // 二进制表示中1的个数
            int count = 0;
            for (int j = 0; j < m; j++) {
                if ((i >> j & 1) == 1) {
                    count++;
                    if (t * p[j] > n) {
                        t = -1;
                        break;
                    }
                    t *= p[j];
                }
            }
            if (t != -1) {
                // 奇数符号是正的，偶数符号是负的
                if ((count & 1) == 1) res += n / t;
                else res -= n / t;
            }
        }
        out.println(res);
        out.flush();
        out.close();
    }