題意：給出N個數和M，求1到M的數中與給出的N個數有大于1的公共因子的數的個數。
思路：算是第一道容斥原理的題吧，1Y、^_^，神搜求最小公倍數奇數個相加、偶數個相減。
題目連結：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2836
View Code
1 #include <cstdio>
2 #include <cmath>
3 #include <cstdlib>
4 #include <cstring>
5 #include <string>
6 #include <algorithm>
7 #include <iostream>
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 } 轉載于:https://www.cnblogs.com/Hug-Sea/articles/2710489.html