Untitled
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 947 Accepted Submission(s): 538
Problem Description
There is an integer a and n integers b1,…,bn. After selecting some numbers from b1,…,bn in any order, say c1,…,cr, we want to make sure that a mod c1 mod c2 mod… mod cr=0 (i.e., a will become the remainder divided by ci each time, and at the end, we want a to become 0). Please determine the minimum value of r. If the goal cannot be achieved, print −1 instead.
Input
The first line contains one integer T≤5, which represents the number of testcases.
For each testcase, there are two lines:
1. The first line contains two integers n and a (1≤n≤20,1≤a≤106).
2. The second line contains n integers b1,…,bn (∀1≤i≤n,1≤bi≤106).
Output
Print T answers in T lines.
Sample Input
2
2 9
2 7
2 9
6 7
2 9
2 7
2 9
6 7
Sample Output
2
-1
-1
Source
本次题目就是个纯暴力搜索的一道题目，唯一一点要注意的就是序列应该先降序排列，为什么呢？(因为如果升序排列的话i<j，Ci小于Cj,Ci先进行取余运算，那么Cj就没有意义了)
除此之外就是简单的深搜，附上本人的代码
#include<stdio.h>
#include<stdlib.h>
#define maxn 30
int min, sum,n;
int a[maxn], b[maxn],c[maxn];
int Min(int a, int b)
{
return a> b ? b:a;
}
int dfs(int m)
{
if (m == n + )
{
int temp = sum;
int length = ;
for (int j = ; j <=n; j++)
{
if (temp == )
break;
if (c[j] == )
{
temp %= a[j];
length++;
}
}
if (temp==)
min = Min(min, length);
return ;
}
//这里利用选择为0，未选为1，方便代码调试时按照二进制运算来看，比较直观
c[m] = ;//用来标记哪些被选了
dfs(m + );
c[m] = ;//标记未被选
dfs(m + );
}
int cmp(const void*a, const void*b)
{
return *(int *)b - *(int*)a;
}
int main()
{
int num;
scanf("%d", &num);
while (num--)
{
min= ;
scanf("%d%d", &n, &sum);
for (int i = ; i <= n; i++)
scanf("%d", &a[i]);
qsort(&a[], n, sizeof(a[]), cmp);
dfs();
if (min!=)
printf("%d\n", min);
else printf("-1\n");
}
}