代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int a[100010], keyi, n;
int bei[100010];
bool dfs(int i, int deep)
{
    if (bei[i] && deep)
        return 1;
    for (int j = 1; j <= n; j++)
        for (int k = 1; k * a[j] <= i; k++)
            if (i >= a[j] * k)
            {
                if (dfs(i - a[j] * k, deep + 1))
                    return 1;	
            }
    return false;
}
inline int read()
{
    int x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
        ch = getchar();
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar();
    return x;
}
int main()
{
//	freopen("money.in", "r", stdin);
//	freopen("money.out", "w", stdout);
    int t;
    scanf("%d", &t);
    while(t--)
    {
        keyi = 0;
        memset(bei, 0, sizeof(bei));
        scanf("%d" ,&n);
        for (int i = 1; i <= n; i++)
            a[i] = read();
        sort(a + 1, a + 1 + n); 
        for (int i = 1; i <= n; i++)
            for (int j = a[i]; j <= 20010; j += a[i])
                bei[j] = 1;					
        for (int i = 1; i <= n; i++)
            if (dfs(a[i], 0))	//如果可以被消， keyi++ 
                keyi++;
        printf("%d\n", n - keyi);
    }
    return 0;
}
/*
1
2
992 50
*/

评测结果