2017.10.7 国庆清北 D7T1 计数

题目描述

给出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]

输出格式：

输出一行，包含1个整数，表示答案

输入输出样例

输入样例#1：

10 2
2 3

输出样例#1：

说明

对于60%的数据，1<=n<=10^6

对于另外20%的数据，m=2

对于100%的数据，1<=n<=10^9,0<=m<=20,1<=a[i]<=10^9

 1 /*
 2 容斥原理
 3 ans=n/单个数-n/两个数lcm+n/三个数lcm-....+(-1)^(i+1)*n/n个数的lcm
 4 复杂度 2^m*log    
 5  
 6 用dfs求各个数的lcm。看了老司机昨天打的T2，我竟然想手模20个数的lcm /捂脸/ 
 7 千万千万要开long long，不知道哪儿需要开的话就全开long long，反正不差那点空间 
 8 */
 9 
10 #include<iostream>
11 #include<cstdio>
12 #include<algorithm>
13 #include<cstring>
14 #include<cmath>
15 using namespace std;
16 
17 long long n,m,ans;
18 long long a[25];
19 
20 int gcd(long long a,long long b)
21 {
22     return b?gcd(b,a%b):a;
23 }
24 
25 void dfs(long long now,int deep,int flag)
26 {
27     if(now>n) return;
28     if(deep==m+1)
29     {
30         ans+=n/now*flag;
31         return;
32     }
33     dfs(now,deep+1,flag);
34     dfs(now/gcd(now,a[deep])*a[deep],deep+1,-flag);
35 }
36 
37 inline void init()
38 {
39     scanf("%lld%lld",&n,&m);
40     for(int i=1;i<=m;i++)
41     {
42         scanf("%lld",&a[i]);
43     }
44     dfs(1,1,1);
45     printf("%lld",ans);
46 }
47 
48 int main()
49 {
50     init();
51     return 0;
52 }

View Code