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

　　题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=1796

　　题目描述：给出n和大小为m的集合，计算小于n的是集和中数的倍数的数的个数

　　解题思路：很好想的容斥......之前因为没看题目输出可能为0WA了一发

　　代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iterator>
#include <cmath>
#include <algorithm>
#include <stack>
#include <deque>
#include <map>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define mem0(a) memset(a,0,sizeof(a))
#define sca(x) scanf("%d",&x)
#define de printf("=======
")
typedef long long ll;
using namespace std;

ll a[30];
ll ans;
int m;
int m1;
ll n;
ll gcd( ll a, ll b ) {
    return b == 0 ? a : gcd( b, a%b );
}

ll lcm( ll a, ll b ) {
    return a * b / gcd(a, b);
}

void dfs( int cur, ll now, int cnt ) {
    if( cnt > m1 ) return;
    ll temp = lcm(a[cur], now);
    if( cnt & 1 ) {
        ans += (n-1)/temp;
    }
    else {
        ans -= (n-1)/temp;
    }
    for( int i = cur+1; i <= m1; i++ ) {
        dfs( i, temp, cnt+1 );
    }
}
int main() {
    while( cin >> n >> m ) {
        ans = 0;
        m1 = 0;
        for( int i = 1; i <= m; i++ ) {
            ll temp;
            cin >> temp;
            if( temp > 0  ) {
                a[++m1] = temp;
            }
        }
        
        for( int i = 1; i <= m1; i++ ) {
            dfs(i, a[i], 1);
        }
        cout << ans << endl;
    }
    
    return 0;
    
}

View Code

　　思考：最近有点儿放羊了.....别咸鱼啊，多看点书，然后仔细读题