程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> BestCoder Round #49 ($) 1001 Untitled

BestCoder Round #49 ($) 1001 Untitled

編輯：C++入門知識

BestCoder Round #49 ($) 1001 Untitled

問題描述

有一個整數aa和nn個整數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。請你得出最小的rr，也就是最少要選擇多少個數字。如果無解，請輸出-1−1.

輸入描述

輸入文件的第一行有一個正整數 T leq 5T≤5，表示數據組數。

接下去有TT組數據，每組數據的第一行有兩個正整數nn和aa (1 leq n leq 20, 1 leq a leq 10^{6}1≤n≤20,1≤a≤10?6??).

第二行有nn個正整數b_1, ldots, b_nb?1??,…,b?n?? (orall 1leq i leq n, 1 leq b_i leq 10^{6}∀1≤i≤n,1≤b?i??≤10?6??).

輸出描述

輸出TT行TT個數表示每次詢問的答案。

輸入樣例

輸出樣例

2
-1

【思路】

對於一組可能的答案cc，如果先對一個覺小的c_ic?i??取模，再對一個較大的c_jc?j??取模，那麼這個較大的c_jc?j??肯定是沒有用的。因此最終的答案序列中的cc肯定是不增的。那麼就枚舉選哪些數字，並從大到小取模看看結果是否是00就可以了。時間復雜度O(2^n)O(2?n??).

代碼：

#pragma comment(linker, /STACK:1024000000,1024000000
//C
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//C++
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

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