題目連結:https://ac.nowcoder.com/acm/problem/14686
題目描述
給出一個集合和一個數m。
集合裡面有n個質數。
請你求出從 1 到 m 的所有數中,至少能被集合中的一個數整除的數的個數。
輸入描述:
第一行兩個正整數 n 和 m 。
第二行n個正整數,分别為集合中的質數。
輸出描述:
輸出一個整數,表示符合要求的正整數的個數。
示例1
輸入
3 37
5 7 13
輸出
13
#include<iostream>
#include<cstdio>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<list>
#include<set>
#include<iomanip>
#include<cstring>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cassert>
#include<sstream>
#include<algorithm>
using namespace std;
#define MAXN 1000005
#define INF 0x3f3f3f3f
typedef long long ll;
int a[25];
int main()
{
ll n,m,ans=0;
scanf("%lld%lld",&n,&m);
for (int i=0; i<n; i++)
scanf("%d",&a[i]);
for (int s=1; s<(1<<n); s++)//取與不取
{
int t=0;//共取了幾個,奇加偶減,容斥原理
long long ss=m;//滿足條件的數的個數
for (int j=0; j<n; j++)
if ((s>>j)&1)//每一位取,或不取
{
t++;
ss/=a[j];
}
//cout<<ss<<endl;
if (t&1)
ans+=ss;
else
ans-=ss;
}
printf("%lld\n",ans);
}