鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > c++ > >

#19. 计数(容斥原理)

来源:互联网 作者:佚名 时间:2018-02-27 09:50
时间限制: 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] 【输出】 输出文

时间限制: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 }

 

 

网友评论
<