题意:
给出一个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;
}