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).
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
Sample Output
2
-1
Source
本次题目就是个纯暴力搜索的一道题目，唯一一点要注意的就是序列应该先降序排列，为什么呢？(因为如果升序排列的话i<j，Ci小于Cj,Ci先进行取余运算，那么Cj就没有意义了)
除此之外就是简单的深搜，附上本人的代码
1 #include<stdio.h> 2 #include<stdlib.h> 3 #define maxn 30 4 int min, sum,n; 5 int a[maxn], b[maxn],c[maxn]; 6 int Min(int a, int b) 7 { 8 return a> b ? b:a; 9 } 10 int dfs(int m) 11 { 12 if (m == n + 1) 13 { 14 int temp = sum; 15 int length = 0; 16 for (int j = 1; j <=n; j++) 17 { 18 if (temp == 0) 19 break; 20 if (c[j] == 0) 21 { 22 temp %= a[j]; 23 length++; 24 } 25 } 26 if (temp==0) 27 min = Min(min, length); 28 return 0; 29 }
//这里利用选择为0，未选为1，方便代码调试时按照二进制运算来看，比较直观 30 c[m] = 0;//用来标记哪些被选了 31 dfs(m + 1); 32 c[m] = 1;//标记未被选 33 dfs(m + 1); 34 } 35 int cmp(const void*a, const void*b) 36 { 37 return *(int *)b - *(int*)a; 38 } 39 int main() 40 { 41 int num; 42 scanf("%d", &num); 43 while (num--) 44 { 45 min= 1000000; 46 scanf("%d%d", &n, &sum); 47 for (int i = 1; i <= n; i++) 48 scanf("%d", &a[i]); 49 qsort(&a[1], n, sizeof(a[1]), cmp); 50 dfs(1); 51 if (min!=1000000) 52 printf("%d\n", min); 53 else printf("-1\n"); 54 } 55 }