BestCoder Round #49 ($) 1001 Untitled

5339  Untitled

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

输入文件的第一行有一个正整数 $T\le 5$，表示数据组数。

接下去有$T$组数据，每组数据的第一行有两个正整数$n$和$a$ (1 \leq n \leq 20, 1 \leq a \leq 10^{6}1≤n≤20,1≤a≤10?6??).

第二行有$n$个正整数b_1, \ldots, b_nb?1??,…,b?n?? (\forall 1\leq i \leq n, 1 \leq b_i \leq 10^{6}?1≤i≤n,1≤b?i??≤10?6??).

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

2
2 9
2 7
2 9
6 7

2
-1

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

代码：

#pragma comment(linker, "/STACK:1024000000,1024000000"
//C
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
//C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

using namespace std;

#define rep(i,j,k) for(int i=(int)j;i<(int)k;++i)
#define per(i,j,k) for(int i=(int)j;i>(int)k;--i)
#define lowbit(a) a&-a
#define Max(a,b) a>b?a:b
#define Min(a,b) a>b?b:a
#define mem(a,b) memset(a,b,sizeof(a))

typedef long long LL;
typedef unsigned long long LLU;
typedef double db;
const int N=1e5;
const int inf=0x3f3f3f3f;

int dir4[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};
int dir8[8][2]= {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
int movv[5][2]= {{1,0},{0,1},{0,0},{-1,0},{0,-1}};

inline LL read()
{
    int c=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){ c=c*10+ch-'0'; ch=getchar();}
    return c*f;
}
bool cmp(const int &x,const int &y)
{
    return x>y;
}
int t,a,n,m;
int num[N];
int ans;
void dfs(int m,int k,int d)///mod,长度，搜索深度
{
    if(m==0) {
        ans=d;
        return;
    }
    if(d>ans){
        return ;
    }
    if(k>=n){
        return;
    }
    dfs(m%num[k],k+1,d+1);
    dfs(m,k+1,d);
}
int main()
{
    t=read();
    while(t--){
       n=read();
       a=read();
       for(int i=0; i<n; ++i){
           num[i]=read();
       }
       sort(num,num+n,cmp);
       ans = inf;
       dfs(a,0,0);
       if(ans==inf) puts("-1");
       else printf("%d\n",ans);
    }
    return 0;
}

BestCoder Round #49 ($) 1001 Untitled

原文：http://blog.csdn.net/u013050857/article/details/47204101