hdu 1796 容斥原理

題目連結：點選打開連結

被這個0坑了好久，題目有沖突，注意這個0就OK了。

題解：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int n,m;
int num[25];
int gcd(int a,int b){
	return b==0? a:gcd(b,a%b);
}
ll solve(){
	ll ans=0;
	for(int i=1;i<(1<<m);i++){
		int sum=1,cnt=0;
		for(int j=0;(1<<j)<=i;j++){
			if((1<<j)&i){
				cnt++;
				sum=sum/gcd(sum,num[j])*num[j];
			}
		}
		if(cnt&1)  ans+=(n-1)/sum;
		else ans-=(n-1)/sum;
	}
	return ans;
}
int main(){
	while(cin>>n>>m){
		for(int i=0;i<m;i++){
			scanf("%d",num+i);
			if(num[i]==0)
			m--,i--;
		}
		printf("%lld\n",solve());
	}
    return 0; 
}