货币系统

题解：若存在一个货币系统的简化拥有与原货币系统不同的货币，先讨论只多出一种货币的情况，假设多出来的是A，那么x*A必然可以被原货币系统表示(x表示大素数)，也就是说原货币系统中必然有A的约数B，添加A不如保留B，所以一个货币系统的简化一定不会添加其它货币
考虑使m尽可能小，那就要让大的面值尽可能多的能被小的面值凑出来
用dp[i]表示i这个面值能否被表示出来，先把面值排序，然后从小到大扫，如果能被表示就跳过，否则从0循环到maxn，对每个面值进行判断能否表示即可。

代码：

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
const int maxn = 110;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9+7;
using namespace std;
int a[maxn];
int dp[25010];
int main()
{
    int t;
    cin>>t;
    while (t--){
        int n;
        cin>>n;
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        dp[0]=1;
        int ans=n;
        for(int i=1;i<=n;i++){
            if(dp[a[i]]){
                ans--;
                continue;
            }
            for(int j=a[i];j<=a[n];j++){
                dp[j]=dp[j]+dp[j-a[i]];
            }
        }
        printf("%d\n",ans);
    }
    return  0;
}