UntitledTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 570Accepted Submission(s): 291
Problem Description
There is an integer and integers . After selecting some numbers from in any order, say , we want to make sure that (i.e., will become the remainder divided by each time, and at the end, we want to become ). Please determine the minimum value of . If the goal cannot be achieved, print instead.
Input
The first line contains one integer, which represents the number of testcases. For each testcase, there are two lines:1. The first line contains two integers and ().2. The second line contains integers ().
Output
Print answers in lines.
Sample Input
22 92 72 96 7
Sample Output
2-1
Source
题目链接：?pid=5339题目大意：重排列bi，问a对重排列的数不断取模最快能为0的取模次数题目分析：其实是水题，，首先对数字小的取完余后再对数字大的取余等于没取，所以先对大数字取余，从大到小排序，因为n很小，DFS随意搜，也可以用状态压缩做，把每个数字选或不选的状态二进制压缩#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int const MAX = 1 << 22;int const INF = 0x3fffffff;int b[25], sta[MAX];int lowbit(int x){return x & (-x);}bool cmp(int a, int b){return a > b;}int main(){int T;scanf("%d", &T);while(T –){memset(sta, 0, sizeof(sta));int n, a;scanf("%d %d", &n, &a);for(int i = 1; i <= n; i++)scanf("%d", &b[i]);sort(b + 1, b + n + 1, cmp);for(int i = 1; i <= n; i++)sta[1 << (i – 1)] = b[i];int cnt, ans = INF;for(int i = 1; i < (1 << n); i++){int tmp = a;cnt = 0;for(int j = i; j > 0; j -= lowbit(j)){tmp %= sta[lowbit(j)];cnt ++;}if(tmp == 0)ans = min(ans, cnt);}if(ans == INF)printf("-1\n");elseprintf("%d\n", ans);}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
诚实是人生绝妙的法宝。虽然对人诚实，
