这个题的关键是质数
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 20;
int n, m;
int p[N];
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i ++ ) cin >> p[i];
int res = 0;
for (int i = 1; i < 1 << m; i ++ )
{
//t表示当前所有质数的乘积,cnt表示当前i中有几个1即当前选法有几个集合
int t = 1, cnt = 0;
for (int j = 0; j < m; j ++ )
if (i >> j & 1) //判断i的第j位是否为1,比如i=5时二进制表示为101,即选择Sp1和Sp3
{
cnt ++ ; //每次i当前位为1,cnt就自增1
//比如计算 (Sp1 ∩ Sp2) 即计算1到n中既能被p1整除又能被p2整除的数的个数
//因为p1和p2都是质数,所以能同时被它俩整除的数最小也是p1*p2,关键是要理解这一点!
//此处只需算出p1与p2的最小公倍数即可,因为最后的 res += n / t 会把余下的加上.
if ((LL)t * p[j] > n)
{
t = -1;
break;
}
t *= p[j];
}
if (t != -1)
{
if (cnt % 2) res += n / t; //有奇数个集合就加上,偶数个集合就减去
else res -= n / t;
}
}
cout << res << endl;
return 0;
}