#19. 计数（容斥原理）
时间限制：1s
内存限制：256MB
【问题描述】
给出m个数a[1],a[2],…,a[m]
求1~n中有多少数不是a[1],a[2],…,a[m]的倍数。
【输入】
输入文件名为count.in。
第一行，包含两个整数：n,m
第二行，包含m个数，表示a[1],a[2],…,a[m]
【输出】
输出文件名为count.out。
输出一行，包含1个整数，表示答案
【输入输出样例】
count.in | count.out |
|---|---|
10 2 2 3 | 3 |
【数据说明】
对于60%的数据，1<=n<=106
对于另外20%的数据，m=2
对于100%的数据，1<=n<=109,0<=m<=20,1<=a[i]<=109
容斥原理
对于三个数的情况
我们需要加上每个数对答案的贡献，减去两两对答案的贡献，加上三三对答案的贡献
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 #include<queue>
7 #define LL long long
8 using namespace std;
9 const LL MAXN=100001;
10 inline void read(LL &n)
11 {
12 char c=getchar();bool flag=0;n=0;
13 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
14 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
15 }
16 LL gcd(LL a,LL b)
17 {
18 return b==0?a:gcd(b,a%b);
19 }
20 LL ans=0;
21 LL a[MAXN];
22 LL n,m;
23 void dfs(LL now,LL num,LL how)
24 {
25 if(num>n) return ;
26 if(now==m+1)
27 {
28 ans+=(n/num)*how;
29 return ;
30 }
31 dfs(now+1,num,how);
32 dfs(now+1,num*a[now]/(gcd(num,a[now])),-how);
33 }
34 int main()
35 {
36 read(n);read(m);
37 for(LL i=1;i<=m;i++)
38 read(a[i]);
39 dfs(1,1,1);
40 printf("%lld",ans);
41 return 0;
42 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-10-19 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读