https://ac.nowcoder.com/acm/problem/14686——集合中的质数（容斥原理）

题目:https://ac.nowcoder.com/acm/problem/14686
思路：运用容斥原理——https://oi-wiki.org/math/inclusion-exclusion-principle
zui'h加上dfs直接推算出结果。
代码：

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<utility>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int N=1e8+5;
const LL mod=1e9+7;
int read() {
    char ch=getchar();int x=0,f=1;
    while(ch<'0' || ch>'9')    {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int gcd_(int a,int b) {return b==0?a:gcd_(b,a%b);}
LL fpow(LL a,LL b) {
    LL res=1;
    while(b) {
        if(b&1) res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
LL a[25],res,m;
int n;
void dfs(LL aa,int i,int cnt) {
    if(aa>m) return;
    if(cnt&1) res+=m/aa;
    else res-=m/aa;
    for(int j=i+1;j<n;++j) {
        dfs(a[j]*aa,j,cnt+1);
    }
}
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
//    cout<<"Accepted!\n";
    cin>>n>>m;
    res=0;
    for(int i=0;i<n;++i) cin>>a[i];
    for(int i=0;i<n;++i) dfs(a[i],i,1);
    cout<<res;
    return 0;
}