欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2018.11.01【NOIP训练】cost数(容斥原理)(DFS)

程序员文章站 2022-05-08 19:01:37
...

传送门


解析:

一眼应该看得出来是一道容斥原理,不然就请回去学习组合数学。

然而我就是不知道容斥怎么实现。。。

学习了一下用DFSDFS枚举每个选择与不选的情况同时更改系数是11还是1-1就行了。

这道题主要的剪枝就是,考虑我们枚举的lcmlcm在某个时刻很容易就超过了上界,这个显然可以直接减掉。


代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register
#define gc getchar
#define pc purchar
#define cs const
#define int ll 

int A[32],n,m;
ll ans=0;
inline ll lcm(ll a,ll b){
	return a/__gcd(a,b)*b;
}

inline void dfs(int pos,int f,ll l){
	if(!pos){
		if(l!=1)
		ans+=m/l*f;
		return ;
	}
	if(l>m)return ;
	dfs(pos-1,f,l);
	dfs(pos-1,-f,lcm(l,A[pos]));
}

inline void solve(){
	sort(A+1,A+n+1);
	for(int re i=1;i<=n;++i){
		if(A[i])
		for(int re j=i+1;j<=n;++j){
			if(A[j]%A[i]==0)A[j]=0;
		}
	}
	int len=0;
	for(int re i=1;i<=n;++i)if(A[i])A[++len]=A[i];
	n=len;
	dfs(n,1,1);
}

signed main(){
	scanf("%lld%lld",&n,&m);m-=17;
	for(int re i=1;i<=n;++i){
		scanf("%lld",&A[i]);
	}
	solve();
	cout<<-ans+1;
	return 0;
}