题意：给出N个数和M，求1到M的数中与给出的N个数有大于1的公共因子的数的个数。
思路：算是第一道容斥原理的题吧，1Y、^_^，神搜求最小公倍数奇数个相加、偶数个相减。
题目链接：
View Code 1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 const int N=11;10 11 int n,m,sum;12 int a[N];13 14 int gcd(int a,int b){15 return b==0?a:gcd(b,a%b);16 }17 18 void dfs(int val,int s,int k,int cnt){19 if(cnt>k) return ;20 if(cnt==k){21 if(cnt%2) sum+=m/val;22 else sum-=m/val;23 return ;24 }25 for(int i=s+1;i<=n;i++){26 dfs(val*a[i]/gcd(val,a[i]),i,k,cnt+1);27 }28 }29 30 int main(){31 32 // freopen("data.in","r",stdin);33 // freopen("data.out","w",stdout);34 35 while(scanf("%d%d",&n,&m)!=EOF){36 for(int i=1;i<=n;i++) scanf("%d",&a[i]);37 sum=0;38 for(int i=1;i<=n;i++){39 dfs(1,0,i,0);40 }41 printf("%d\n",sum);42 }43 }