C - How many integers can you find（容斥原理&暴力）

C - How many integers can you find（容斥原理&暴力）

思路：暴力或者搜索，因为$M$M最大只有10,根据容斥原理可以用选出的元素个数计算对答案的贡献，奇数就加，偶数就减。

AC代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=1e5+5;
#define mst(a) memset(a,0,sizeof a)
int a[15],n,m,ans,cnt;
int main(){
	while(~scanf("%d%d",&n,&m)){
		ans=cnt=0; 
	for(int i=0,x;i<m;i++){
		scanf("%d",&x);
		if(x) a[cnt++]=x;
	}
	for(int i=1;i<(1<<cnt);i++){ //暴力所有情况. 
		int f=0,g=1;
		for(int j=0;j<cnt;j++){
			if((i>>j)&1){
				f++;
				g=g/__gcd(g,a[j])*a[j];//lcm 
			}
		}
		if(f&1) ans+=(n-1)/g; //元素个数的奇偶性 
		else ans-=(n-1)/g;
	}
	printf("%d\n",ans);
	} 
	return 0;
} 
 

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=1e5+5;
#define mst(a) memset(a,0,sizeof a)
int a[15],n,m,ans,cnt;
void dfs(int id,int x,int tot){ //遍历以a[id]开头的所有组合对答案的贡献. 
	 x=x/__gcd(x,a[id])*a[id];    //以a[0]为例,    |0|0,1|0,1,2|0,1,2|0,1,2,3|0,1,3|0,2|0,2,3|0,3 
	 if(tot&1) ans+=(n-1)/x;
	 else ans-=(n-1)/x;
	 for(int i=id+1;i<cnt;i++)
	 	dfs(i,x,tot+1);
}
int main(){
	while(~scanf("%d%d",&n,&m)){
			ans=cnt=0; 
	for(int i=0,x;i<m;i++){
		scanf("%d",&x);
		if(x) a[cnt++]=x;
	}
		for(int i=0;i<cnt;i++)
			dfs(i,a[i],1);
		printf("%d\n",ans); 
	}
	return 0;
}