Untitled

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

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

T answers in

T lines.

Sample Input

Sample Output

Source

BestCoder Round #49 ($)

/************************************************************************/

附上该题对应的中文题

Untitled

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

问题描述

有一个整数 $a$ 和 $n$ 个整数 $b_1, \ldots, b_n$ 。在这些数中选出若干个数并重新排列，得到 $c_1, \ldots, c_r$ 。我们想保证 $\ mod \ c_1 \ mod \ c_2 \ mod \ldots \ mod \ c_r = 0$ 。请你得出最小的 $r$ ，也就是最少要选择多少个数字。如果无解，请输出 $? 1$ .

输入描述

输入文件的第一行有一个正整数  $\leq 5$ ，表示数据组数。接下去有 $T$ 组数据，每组数据的第一行有两个正整数 $n$ 和 $a$  ( $\leq n \leq 20, 1 \leq a \leq 10^{6}$ ).第二行有 $n$ 个正整数 $b_1, \ldots, b_n$  ( $\forall 1\leq i \leq n, 1 \leq b_i \leq 10^{6}$ ).

输出描述

输出 $T$ 行 $T$ 个数表示每次询问的答案。

输入样例

输出样例

2
-1

/****************************************************/

出题人的解题思路：对于一组可能的答案 $c$ ，如果先对一个较小的 $c_i$ 取模，再对一个较大的 $c_j$ 取模，那么这个较大的 $c_j$ 肯定是没有用的。因此最终的答案序列中的 $c$ 肯定是不增的。那么就枚举选哪些数字，并从大到小取模看看结果是否是 $0$ 就可以了。时间复杂度 $O(2^n)$ .

对于上述红色字体处的解释：例如9%7==2，若此时再对比2大的数取模，比如2%6==2，这是无意义的，而且导致选择的数反而多了。

本人的做法是，先对b数组排序，复杂度O(nlogn)，然后利用深搜从大到小搜比余数小的值，或许不太好理解，直接上AC代码吧

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<iostream>
#define exp 1e-10
using namespace std;
int s[25],a,Min,k,n;
void DFS(int b,int t,int k)
{//printf("%d %d %d\n",b,s[t],k);if(k>Min)return ;if(b==0){Min=min(Min,k);return ;}for(int i=t-1;i>=1;i--)if(b>=s[i]){//printf("%d %d\n",b,s[i]);DFS(b%s[i],i,k+1);}
}
int main()
{int t,i;scanf("%d",&t);while(t--){Min=25;scanf("%d%d",&n,&a);for(i=1;i<=n;i++)scanf("%d",&s[i]);sort(s+1,s+n+1);DFS(a,n+1,0);if(Min!=25)printf("%d\n",Min);elseprintf("-1\n");}return 0;
}

用时0MS

HDU 5339 Untitled ——BestCoder Round #49

Untitled

Untitled