HDU 5339 Untitled

给你N个数和一个数a，问最少从N个数中取出多少个数,满足a%x1%x2%x3…xr=0。不存在则输出-1。

题目链接HDU 5339

题目解析

DFS，将数组排序，从大到小搜索，记录现在的余数，搜索的位置，层数。

AC代码

#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
int x[21];
int n,a;
int ans;
void dfs(int a,int pos,int num) //余数，位置，层数
{
        for(int i=pos-1;i>=0;i--)
        {
                if(a%x[i]==0)
                {
                        if(num<ans) //找到搜索过程中最小的层数
                        {
                                ans=num;
                        }
                }
                dfs(a%x[i],i,num+1);
        }
}
int main()
{
        int t;
        cin>>t;
        while(t--)
        {
                cin>>n>>a;
                for(int i=0;i<n;i++)
                {
                        cin>>x[i];
                }
                sort(x,x+n);
                ans=n+1;
                dfs(a,n,1);
                if(ans==n+1) //层数没变，说明无法满足条件
                {
                        cout<<"-1"<<endl;
                }
                else
                {
                        cout<<ans<<endl;
                }
        }
        return 0;
}