题目描述

这个题目简化来说就是就（n，a）里面有多少种货币是无用的可以去掉的，就是化简一下这个货币系统，如果有3那么6，9等等倍数就是无用的，如果有2，3那么5就是无用的，因为货币大小小于M，所以我们可以求小于M的所有数字用这套货币系统来表示的方案数，接下来遍历（n，a）如果ai这个数字在这套货币系统下只能有1种表示方式就是ai了也就是说它不可被替换，于是我们要求的数量++，然后就得出结果了。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e2+10;
const int M = 25000;
int dp[M],a[N];
int n,m;
signed main()
{
   int T;cin>>T;
   while(T--){
       cin>>n;
  for(int i=1;i<=n;i++)cin>>a[i];memset(dp,0,sizeof dp);
    dp[0] = 1;
    for(int i=1;i<=n;i++)
        for(int j=a[i];j<=M;j++)
            dp[j] += dp[j-a[i]];
    int res=0;

   for(int j=1;j<=n;j++)
   if(dp[a[j]] == 1)res++;
   cout<<res<<"\n";
   }
}