这题是跟竹子compare时发现的，一直不会打代码，今天狠狠心学了学，打完了，可以加到模板里了。
/* * hdu1796/win.cpp * Created on: 2012-8-20 * Author : ben */ #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <ctime> #include <iostream> #include <algorithm> #include <queue> #include <set> #include <map> #include <stack> #include <string> #include <vector> #include <deque> #include <list> #include <functional> #include <numeric> #include <cctype> using namespace std; const int MAXM = 15; typedef long long LL; int N, M, data[MAXM]; LL gcd(LL a, LL b) { LL r; while(b) { r = a % b; a = b, b = r; } return a; } LL getlcm(LL a, LL b) { LL c = gcd(a, b); return a / c * b; } /** * now当前点序号 * count加入容斥的个数 */ void dfs(int now, int count, LL lcm, LL &ans) { lcm = getlcm(lcm, data[now]); if(count % 2 == 0) { ans -= (N - 1) / lcm; }else { ans += (N - 1) / lcm; } for(int i = now + 1; i < M; i++) { dfs(i, count + 1, lcm, ans); } } LL work(int N, int M) { LL ans = 0; for(int i = 0; i < M; i++) { dfs(i, 1, data[i], ans); } return ans; } int main() { #ifndef ONLINE_JUDGE freopen("data.in", "r", stdin); #endif while(scanf("%d%d", &N, &M) == 2) { int m = 0; for(int i = 0; i < M; i++) { scanf("%d", &data[m]); if(data[m] > 0) { m++; } } M = m; printf("%I64d\n", work(N, M)); } return 0; }