HDU 5339 Untitled

Problem Description

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

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

2
2 9
2 7
2 9
6 7

Sample Output

2
-1

暴力枚举就好了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int maxn = 100005;
int T, n, m, a[maxn], ans;

void dfs(int x, int y, int z)
{
    if (!y) { 
        if (ans < 0) ans = z;
        else ans = min(ans, z); 
        return;
    }
    if (!x) return;
    if (ans>=0&&z>=ans) return;
    dfs(x - 1, y%a[x], z + 1);
    dfs(x - 1, y, z);
}

int main()
{
    cin >> T;
    while (T--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        sort(a + 1, a + n + 1);
        ans = -1;
        dfs(n, m, 0);
        printf("%d\n", ans);
    } 
    return 0;
}