HDU 1796 How many integers can you find（容斥原理）

http://acm.hdu.edu.cn/showproblem.php?pid=1796

这篇文章对容斥原理讲解很清楚 http://www.cppblog.com/vici/archive/2011/09/05/155103.html

View Code

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<string.h>
 4 #include<cmath>
 5 #define LL long long
 6 using namespace std;
 7 LL sum,x[21],n;
 8 int m;
 9 int gcd(int x,int y)
10 {
11     return y==0?x:gcd(y,x%y);
12 }
13 void dfs(int num,int i,LL y)
14 {
15     int j;
16     y = y*x[i]/(gcd(y,x[i]));
17     if(num%2!=0)
18     sum+=(n-1)/y;
19     else
20     sum-=(n-1)/y;
21     for(j = i+1 ; j <= m ; j++)
22     {
23         if(x[j]!=0)
24         dfs(num+1,j,y);
25     }
26 }
27 int main()
28 {
29     int i,j,k;
30     while(cin>>n>>m)
31     {
32         sum = 0;
33         for(i = 1; i <= m ; i++)
34         cin>>x[i];
35         for(i = 1 ; i <= m ; i++)
36         {
37             if(x[i]!=0)
38             dfs(1,i,x[i]);
39         }
40         cout<<sum<<endl;
41     }
42     return 0;
43 }