容斥原理
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
题目思路
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();
}