--bestcoder

Untitled

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 774    Accepted Submission(s): 423

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

 

Sample Output

2 -1

 

不知道为什么必须判断比他大的数啊，老是超时，判断了就不超时了。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int t ;
int n,a;
int x[25];
bool cmp(int a,int b){
return a >b;
}
int dfs(int u,int depth){
if(u == 0)return depth;
int minn  = n+1;
for(int i = depth;i<n;i++){
int z = u>=x[i]?dfs(u % x[i],depth+1):n+1;
if( z < minn)minn = z;
}
return minn;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&a);
for(int i = 0;i<n;i++){
scanf("%d",&x[i]);
}
sort(x,x+n,cmp);
int minn = n+1;
for(int i = 0;i<n;i++){
int z = a >= x[i]?dfs(a % x[i],1):n+1;
if( z < minn) minn = z;
}
printf("%d\n",minn == n+1?-1:minn);
}
}