Acwing 890. 能被整除的数

题目描述

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

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

输入格式

第一行包含整数 n 和 m。

第二行包含 m个质数。

输出格式

输出总共的个数。

数据范围

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

思路

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

代码

#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>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 ;
}

-= n /flag ;
}
}

cout<< ans ;return   0 ;

}