天天看点

hdu5339(暴力)

题意:

给出一个a,还有n个数字;

然后从n个数字中选出r个排列;

要求a % c1 % c2 % c3......%cr = 0;

问最少选几个;

思路:

首先取余肯定要先取余大的,因为取余完小的,再取余大的,肯定等于本身;

所先先从大到小排序;

才20,暴搜;

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 25;
const int INF = 0x3f3f3f3f;
int n, a, ans, b[N];

bool cmp(int a, int b) {
	return a > b;
}

void dfs(int cur, int num, int cnt) {
	if (cur == 0) {
		ans = min(ans, cnt);
		return ;
	}
	if (num == n)
		return;
	dfs(cur % b[num], num + 1, cnt + 1);
	dfs(cur, num + 1, cnt);

}
int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		ans = INF;
		scanf("%d%d", &n, &a);
		for (int i = 0; i < n; i++) {
			scanf("%d", &b[i]);
		}
		sort(b, b + n, cmp);
		dfs(a, 0, 0);
		if (ans != INF)
			printf("%d\n", ans);
		else
			puts("-1");
	}
	return 0;
}