AcWing 890. 能被整除的数
原题链接
简单
作者:
xhalz_syx
,
2023-11-13 18:18:51
,
所有人可见
,
阅读 53
//这题考虑容斥,还是比较简单的
#include <cstdio>
using namespace std;
typedef long long LL;
int p[20];
int n, m;
LL ans;
void dfs(int depth, LL sp, int x)
{
if (depth > m) return;
if (sp > n) return;
if (depth & 1)
{
ans += n / sp;
}
else if (depth)
{
ans -= n / sp;
}
for (int i = x; i <= m; i ++ )
{
dfs(depth + 1, sp * p[i], i + 1);
}
return;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i ++ ) scanf("%d", &p[i]);
dfs(0, 1, 1);
printf("%lld", ans);
return 0;
}