?
?
问题描述
有一个整数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
2 9
2 7
2 9
6 7
输出样例
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