BestCoderRound#49Untitled/hdu5339（搜索）

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)

​

Total Submission(s): 840Accepted Submission(s): 472

Problem Description

aand nintegers b1,…,bn. After selecting some numbers from b1,…,bnin any order, say c1,…,cr, we want to make sure that amodc1modc2mod…modcr=0(i.e., awill become the remainder divided by cieach time, and at the end, we want ato become 0). Please determine the minimum value of r. If the goal cannot be achieved, print −1instead.

Input

T≤5, which represents the number of testcases.

For each testcase, there are two lines:

1. The first line contains two integers nand a( 1≤n≤20,1≤a≤106).

2. The second line contains nintegers b1,…,bn( ∀1≤i≤n,1≤bi≤106).

Output

Tanswers in Tlines.

Sample Input

2 2 9 2 7 2 9 6 7

Sample Output

2 -1

Source

​​BestCoder Round #49 ($)​​

Recommend

hujie|We have carefully selected several similar problems for you: ​​5342​​​ ​​​5341​​​ ​​​5340​​​ ​​​5339​​​ ​​​5338​​

解析：直接暴力搜索就好了。

第一次提交时，惊喜的发现居然排在第二位，exe.memory为1416kb，然后不断测试，显示删掉多余变量，然后又直接把对输入数据的排序给去掉，就排第一了，好开森。。。。。

代码：

<span style="font-size:14px;">#include<cstdio>
#include<algorithm>
using namespace std;

int a[30],n,m,ans;

void dfs(int step,int x)
{
  if(step>=ans)return;
  for(int i=1;i<=n;i++)
   {
     if(x%a[i]==0){ans=step;return;}
     if(x>a[i])dfs(step+1,x%a[i]);
   }
}

int main()
{
  int i,j,t;
  while(scanf("%d",&t)==1)
    for(i=1;i<=t;i++)
      {
        scanf("%d%d",&n,&m);
        for(j=1;j<=n;j++)scanf("%d",&a[j]);
        ans=30,dfs(1,m);
        if(ans==30)printf("%d\n",-1);
        else printf("%d\n",ans);
      }
  return 0;
}</span>