How many integers can you find

12 2
2 3

7

题目链接:点击打开链接

给出n, m, n代表1 - n的一个序列, 接下来m个数组成的集合, 问序列中能够整除任一集合中的一个数的个数和为多少.

对读入的m个数进行推断, 非0则赋值到a数组中, 进行dfs, dfs时进行容斥运算, id为奇数则加, 为偶数则减去反复的.

AC代码:

#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "queue"
#include "stack"
#include "cmath"
#include "utility"
#include "map"
#include "set"
#include "vector"
#include "list"
#include "string"
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int MAXN = 15;
int n, m, num, ans, a[MAXN];
int gcd(int a, int b)
{
	return b == 0 ? a : gcd(b, a % b);
}
void dfs(int cur, int lcm, int id)
{
	lcm = a[cur] / gcd(a[cur], lcm) * lcm;
	if(id & 1) ans += (n - 1) / lcm;
	else ans -= (n - 1) / lcm;
	for(int i = cur + 1; i < num; ++i)
		dfs(i, lcm, id + 1);
}
int main(int argc, char const *argv[])
{
	while(scanf("%d%d", &n, &m) != EOF) {
		num = ans = 0;
		while(m--) {
			int x;
			scanf("%d", &x);
			if(x != 0) a[num++] = x;
		}
		for(int i = 0; i < num; ++i)
			dfs(i, a[i], 1);
		printf("%d\n", ans);
	}
	return 0;
}