n个集合的容斥其实就是 总的 减去两两相交的 加上三个相交 减去四个相交 加上五个.....(奇加偶减)
这道题就是一个lcm的容斥
我们用搜索来实现 枚举选的数
需要加个剪枝 当前lcm已经超过了m
#include<bits/stdc++.h> #define N 35 #define int long long using namespace std; int n,m,a[N],ans; inline int gcd(int x,int y) { if(y==0) return x; return gcd(y,x%y); } inline int lcm(int x,int y) { return x/gcd(x,y)*y; } void dfs(int now,int sum,int num) { if(sum>m) return; if(now==n+1) return; int x=lcm(sum,a[now]); if(num&1) ans+=m/x; else ans-=m/x; dfs(now+1,x,num+1); //选 dfs(now+1,sum,num); //不选 } inline bool cmp(const int &a,const int &b){ return a>b; } main() { cin>>n>>m; if(m>17) m-=17; for(int i=1;i<=n;i++) cin>>a[i]; dfs(1,1,1); cout<<++ans; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9888548.html
