Untitled
There is an integer aaa and nnn integers b1,…,bnb_1, ldots, b_nb1,…,bn. After selecting some numbers from b1,…,bnb_1, ldots, b_nb1,…,bn in any order, say c1,…,crc_1, ldots, c_rc1,…,cr, we want to make sure that a mod c1 mod c2 mod… mod cr=0a mod c_1 mod c_2 mod ldots mod c_r = 0a mod c1 mod c2 mod… mod cr=0 (i.e., aaa will become the remainder divided by cic_ici each time, and at the end, we want aaa to become 000). Please determine the minimum value of rrr. If the goal cannot be achieved, print −1-1−1 instead.
The first line contains one integer T≤5T leq 5T≤5, which represents the number of testcases.
For each testcase, there are two lines:
-
The first line contains two integers nnn and aaa (1≤n≤20,1≤a≤1061 leq n leq 20, 1 leq a leq 10^61≤n≤20,1≤a≤106).
-
The second line contains nnn integers b1,…,bnb_1, ldots, b_nb1,…,bn (∀1≤i≤n,1≤bi≤106forall 1leq i leq n, 1 leq b_i leq 10^6∀1≤i≤n,1≤bi≤106).
Print TTT answers in TTT lines.
2 2 9 2 7 2 9 6 7
2 -1
运用二进制的思想,去枚举每种可能的情况,然后算下最小的。当然,先把比 a 大的数筛掉
#include <iostream> #include <algorithm> using namespace std; int main() { int T; cin >> T; int n, a, b[25], i, cnt; while(T--) { int Min = 50; bool tag = false; cin >>n >> a; for(int i = 0; i < n; ++i) cin >> b[i]; sort(b, b+n); for(i = n-1; i >= 0; --i) { if(a >= b[i]) break; } if(i == 0) { if(a % b[0] == 0) cout << 1 << endl; else cout << -1 << endl; } else { for(int j = 1; j < (1 << (i+1)); ++j) { int tmp = a; cnt = 0; for(int k = i; k >= 0 ; --k) { if((1 << k) & j) { tmp %= b[k]; cnt++; //cout << j << " " <<tmp << " " << b[k] << " "<<cnt << endl;; } } if(tmp == 0) { Min = min(Min, cnt); tag = true; } } if(tag) cout << Min << endl; else cout << -1 << endl; } } return 0; }