Description
给你 (M) 个质数,求 ([1,N]) 中能被这些质数中任意一个整除的数的个数。
Input
第一行两个整数 (N,M) 。
接下来一行 (M) 个质数。
Output
一行一个整数代表答案。
Sample
Sample Input
10 2
2 3
Sample Output
7
Limit
对于 (30\%) 的数据, (1le Nle 10^5) 。
对于 (60\%) 的数据,(1le Mle 10) 。
对于 (100\%) 的数据, (1le Nle 10^9,1le Mle 32)
Solution
搜索,容斥。
为什么这样是对的呢?因为最小的 (8) 个质数的乘积已经大于 (10^9) 了,所以复杂度没锅
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i <= b; i++)
int n, m, p[33], ans;
void dfs(int pos, int cnt, int sum) {
if(cnt & 1) ans -= n / sum; else ans += n / sum;
rep(i, pos, m) if(n / p[i] >= sum) dfs(i + 1, cnt + 1, sum * p[i]);
}
int main() {
freopen("moli.in", "r", stdin); freopen("moli.out", "w", stdout);
scanf("%d%d", &n, &m);
rep(i, 1, m) scanf("%d", &p[i]);
sort(p + 1, p + 1 + m); m = unique(p + 1, p + 1 + m) - p - 1;
dfs(1, 0, 1);
cout << n - ans;
return 0;
}