这题我们要这么考虑：

如果一种货币可以被另外的一种或多种货币表示的话，那么这种货币明显就是不必要的。

而答案，明显就是所有必要货币的个数。

那么，我们来考虑下怎么做。

首先，很容易发现的是，面值最小的货币一定是必要的，因为它不可能被其它货币表示。

然后，我们再同样的，看面值次小的，这时，我们有两种情况：

1.次小的可以被最小的表示，即次小的是最小的倍数。那么次小的就是不必要的

2.次小的不能被最小的表示，那么明显，它也就不能被其它的货币表示了，所以它就是必要的

那么，我们就可以按这个思路依次推导下去。。。

我们设dp[i]表示面值i能否被当前的已选择的必要货币表示

我们先将所有货币的面值由小到大排个序，然后，每次，我们看看当前的货币能否被之前的货币表示，若能，那么这个货币就是不必要的，我们不管它。若不能，则这个货币就是必要的，那么，我们把它添加进我们的货币系统中，并同时更新dp数组，就行了。

考场代码:

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+1,M=101;
int a[M],e;
bool vis[N];
int main(){
//    freopen("money.in","r",stdin);
//    freopen("money.out","w",stdout);
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
            scanf("%d",&a[i]);
        }
        sort(a+1,a+n+1);
        memset(vis,0,sizeof(vis));
        e=0;
        e++;
        vis[a[1]]=1;
        for(int i=2;i<=a[n]/a[1];++i){
            vis[i*a[1]]=1;
        }
        for(int i=2;i<=n;++i){
            if(vis[a[i]]){
                continue;
            }
            e++;
            vis[a[i]]=1;
            for(int j=a[i]+1;j<=a[n];++j){
                if(!vis[j]&&vis[j-a[i]]){
                    vis[j]=1;
                }
            }
        }
        printf("%d\n",e);
    }
    return 0;
}