容斥原理

加法原理的延申
韦恩图，奇加偶减

并转交

许多问题都有“交比并简单的性质”

例题

890. 能被整除的数

给定一个整数 n 和 m 个不同的质数 p1,p2,…,pm。

请你求出 1∼n 中能被 p1,p2,…,pm 中的至少一个数整除的整数有多少个。

输入格式
第一行包含整数 n 和 m。

第二行包含 m 个质数。

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

数据范围
1≤m≤16,
1≤n,pi≤109
输入样例：
10 2
2 3
输出样例：
7

思路
利用容斥原理
1-n中能被pi整除的数有 n / pi 个
这其中可能存在数val，既能被pi整除，又能被pj整除，被加了两次，所有要减去 **n / pi * pj**
…
以此类推

问题来了，如何能遍历所有p的乘积？
p1, p2, … pk
p1p2, p1p3, … pk-1pk
…
p1p2p3…pk

利用二进制位0和1表示每一个pi存在与否，这样m个质数就能用m个二进制位表示有无了！
例如 m = 15 直接用i从1开始，遍历到15，每次加一即可。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[] p = new int[m];
        for (int i = 0; i < m; i++) {
            p[i] = sc.nextInt();
        }
        int res = 0;
        //注意i从1开始
        for (int i = 1; i < (1 << m); i++) {
            int t = 1, cnt = 0;
            for (int j = 0; j < m; j++) {
                if ((i >> j & 1) == 1) {
                    cnt++;
                    //出界，集合中已经没有该数字了
                    if ((long) t * p[j] > n) {
                        t = -1;
                        break;
                    }
                    t *= p[j];
                }
            }
            if (t != -1) {
                if ((cnt & 1) == 1) res += n / t;
                else res -= n / t;
            } 
        }
        System.out.println(res);
    }
}

例1：用容斥原理求解错位排列的数量
例如，长度为4的错位排列的数量。

例2：求
，其中指莫比乌斯函数