HDU 1796 How many integers can you find 容斥、lcm

題意：

輸入n和m個數。問你小于n中，有幾個數能夠被m個數中的任意一個整除的。

思路：

容斥+lcm（最小公倍數）

設m數組中結果為｛a1，a2，a3，……，am｝;

1.加上n/a1，n/a2，n/a3……的個數。

2.減去n/lcm(a1,a2)，n/lcm(a1*a3)，……，n/lcm(a2*a3)，n/lcm(a2*a4),……；

3.加上三個集合的，然後減去四個集合的，加上五個集合的……

因為m最大為10，是以直接用二進制枚舉即可，我用了dfs進行枚舉。

code：

#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long LL;

int n, m;
LL res;
int a[15];
inline LL gcd(LL sum, LL t)
{
	return t?gcd(t, sum%t) : sum;
}
inline LL lcm(LL sum, LL t)
{
	return sum/gcd(sum, t) * t;
}
void dfs(int cnt, int index, LL sum)
{
	if(index == m)
	{
		if(cnt != 0 && sum != 0)
		{
			if(cnt%2)
				res += (LL)n/sum;
			else
				res -= (LL)n/sum;
		}
		return ;
	}
	dfs(cnt+1, index+1, lcm(sum, a[index]));
	dfs(cnt, index+1, sum);
}
	
void solve()
{
	res = 0;
	dfs(0, 0, 1);
	printf("%I64d\n", res);
}
	
int main()
{
	while(scanf("%d%d", &n, &m) != EOF)
	{
		n--;
		for(int i = 0;i < m; i++)
			scanf("%d", &a[i]);
		solve();
	}
	return 0;
}