hdu1796 How many integers can you find----容斥原理

How many integers can you findTime Limit: 12000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2286    Accepted Submission(s): 629


Problem DescriptionInputOutputSample InputSample OutputAuthorSourceRecommend#include<iostream>#include<cstdlib>#include<stdio.h>#define ll __int64using namespace std;int a[15];ll res,n;int m;int gcd(int x,int y){ if(y==0) return x; return gcd(y,x%y);}int lcm(int x,int y){ return x/gcd(x,y)*y;}void dfs(int now,int step,int k){ if(step==m+1) return ; for(int i=step;i<=m;i++) { if(a[i]!=0) { int temp=lcm(now,a[i]);//应该是最小公倍数，而不是乘积，一开始nc了~ int ans=n/temp; if(n%temp==0) ans--; if(k%2) res+=ans; else res-=ans; dfs(temp,i+1,k+1); } }}int main(){ while(scanf("%I64d%d",&n,&m)!=EOF) { res=0; for(int i=1;i<=m;i++) { scanf("%d",&a[i]); if(a[i]!=0) { int num=n/a[i]; if(n%a[i]==0) num--; res+=num; } } for(int i=1;i<=m;i++) { if(a[i]!=0) dfs(a[i],i+1,0); } printf("%I64d\n",res); }}