Acwing 890. 能被整除的数

题目描述

给定一个整数 n 和 m 个不同的质数 p1,p2,…,pm。

请你求出 1∼n中能被 p1,p2,…,pm 中的至少一个数整除的整数有多少个。

输入格式

第一行包含整数 n 和 m。

第二行包含 m个质数。

输出格式

输出总共的个数。
1

数据范围

1≤m≤16,
1≤n,pi≤109

思路

若干个集合组成一个图，集合的大小就是集合内的整数的个数，如果各个集合没有交集，那么各个集合的和就是总集。
如果只有两个集合有交集。那么总集的大小就是各个集合的和减去这两个集合的交集。若是三个集合有公共的集合就是将各个集合相加减去。然后减去所有两两交集加上所有三个集合的交集。以此类推。对于奇数个集合就是加上交集。偶数个集合就是减去若干个集合的交集。
所有这个题目可以看成总集是能够被其中一个数整除的数。
然后里面有若干个集合。对应每个集合就是一个能被该数整除的所有在范围内的数字的集合。

代码

#include
using namespace std;
#include
#include

const int N = 20;
int f[N];

int main()
{
    int n ,m;
    cin>>n>>m;
    for(int i = 0; i < m; i ++ )
    {
        cin>>f[i];
    }
    
    int ans = 0;
    for(int i = 1 ; i < 1 << m ; ++ i)
    {
        int flag = 1 ;
        
        int ti = 0;
        
        for(int j = 0 ; j < m ; ++ j)
        
        {
            if(i >> j & 1 )
            {
                    if((long long)flag *f[j] > n)
                    {
                        flag = - 1 ;
                       break;   
                    } 
                    ti++; 
                    flag *= f[j];
            }
        }
        
        if( flag != -1)
        {
        if( ti % 2)
        ans += ( n/flag);
        else 
        ans -= n /flag ;
        }
    }

    cout<< ans ;
    
    return   0 ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

-= n /flag ;
}
}

cout<< ans ;

return   0 ;
1
2
3

}