容斥原理

2020-03-07

数据结构与算法

字数统计: 213字 | 阅读时长≈ 1分钟

容斥原理的总结

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

1	#include<bits/stdc++.h>
2	using namespace std;
3	typedef long long ll;
4	ll n, m, a[15], ans, p;
5	ll lcm(ll a, ll b){return a * b / __gcd(a, b);}
6	void dfs(ll x, ll sum, ll num)
7	{
8	if(num > m)return;
9	if(num % 2 == 1){ans += (n - 1) / sum;}
10	if(num % 2 == 0){ans -= (n - 1) / sum;}
11	for(ll i = x + 1; i < m; i++)
12	{
13	dfs(i, lcm(sum, a[i]), num + 1);
14	}
15	return ;
16	}
17	int main()
18	{
19	while(scanf("%lld %lld", &n, &p) != EOF)
20	{
21	m = 0;
22	for(ll i = 0; i < p; i++)
23	{
24	scanf("%lld", &a[m++]);
25	if(a[i] == 0 \|\| a[i] > n)m--;
26	}
27	ans = 0;
28	ll flag = 0;
29	for(ll i = 0; i < m; i++)
30	{
31	dfs(i, a[i], 1);
32	if(n % a[i] == 0)flag = 1;
33	}
34	printf("%lld\n", ans);
35	}
36	return 0;
37	}

请我喝杯咖啡吧~

支付宝

微信