【分析】
本题如果使用暴力枚举的话时间复杂度为($O(nm)$),必定$TLE$,因此需要使用容斥原理求解。
什么是容斥原理?
假设有集合:$S_1,S_2,S_3$,那么有如下式子成立:
$|S_1\cup S_2\cup S_3|$
$=|S_1|+|S_2|+|S_3|-|S_1\cap S_2|-|S_1\cap S_3|-|S_2\cap S_3|+|S_1\cap S_2\cap S_3|$
即枚举所有集合的不同交集组合,若组合中集合的个数为奇数那么系数为$1$否则为$-1$,所有集合并集的元素个数即为以上不同交集组合的元素个数之和(注意系数正负)。
回到本题,对于$1\sim n$,假设能被$p_i$整除的数的集合为$S_{p_i}$,那么求解的答案即为:$|S_{p_1}\cup S_{p_2}\cup \dots \cup S_{p_m}|$。
每个集合实际上并不需要知道具体元素是什么,只要知道这个集合的大小,大小为$|S_i|=n/p_i$, 比如题目中$|S_1|=10/2=5,|S_2|=10/3=3$。
交集的大小如何确定?因为$p_i$均为质数,这些质数的乘积就是他们的最小公倍数,$n$除这个最小公倍数就是交集的大小,故$|S_1\cap S_2|=n/(p_1∗p_2)=10/(2∗3)=1$。
如何表示每个集合的状态?考虑到集合数最多为$m(m\le 16)$,因此可用一个$16$位二进制数的每一位来分别表示每个集合的状态,$1$表示选择该集合,$0$表示不选,枚举$1\sim 2^m-1$即可表示所有不同集合的组合方式。
【代码】
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 20;
int p[N];
int n, m;
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i++) cin >> p[i];
LL res = 0;
//枚举1~2^m-1,表示所有集合组合的状态
for (int i = 1; i < 1 << m; i++)
{
LL t = 1, cnt = 0;//t表示选中的集合的最小公倍数,cnt表示组合中的集合数
for (int j = 0; j < m; j++)//枚举i的每一位,即每一个集合的状态
if (i >> j & 1)//如果第j位为1说明组合中有p[j]这个集合
{
cnt++;
t *= p[j];
if (t > n)//如果最小公倍数大于n就没必要继续计算了
{
t = -1;
break;
}
}
if (t != -1)
if (cnt % 2) res += n / t;//如果是奇数个集合那么结果是加上集合中元素的个数
else res -= n / t;//否则是减去集合中元素的个数
}
cout << res << endl;
return 0;
}