4、容斥定理

AcWing 890. 能被整除的数

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.init();
    }

    //容斥原理
    int N = 20;
    int p[] = new int[N];
    int n, m;

    int rongchi() {
        int res = 0;
        for (int i = 1; i < 1 << m ; i ++) {
            //t代表分母的pi*pj*.....
            //s代表有几个p被选中
            int t = 1, s = 0;
            for (int j = 0; j < m; j++) {
                //j位置被光荣选择
                if ((i >> j & 1) == 1) {
                    if((long)t*p[j]>n){
                        t=-1;
                        break;
                    }
                    t*=p[j];
                    s++;
                }
            }
            if(t!=-1){
                if(s%2!=0) res+=n/t;
                else res-=n/t;
            }

        }
        return res;
    }

    void init() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            p[i] = sc.nextInt();
        }
        int res=rongchi();
        System.out.println(res);
    }
}