2021-09-08

532. 貨币系統

在網友的國度中共有 n 種不同面額的貨币，第 i 種貨币的面額為 a[i]，你可以假設每一種貨币都有無窮多張。

為了友善，我們把貨币種數為 n、面額數組為 a[1…n] 的貨币系統記作 (n,a)。

在一個完善的貨币系統中，每一個非負整數的金額 x 都應該可以被表示出，即對每一個非負整數 x，都存在 n 個非負整數 t[i] 滿足 a[i]×t[i] 的和為 x。

然而，在網友的國度中，貨币系統可能是不完善的，即可能存在金額 x 不能被該貨币系統表示出。

例如在貨币系統 n=3, a=[2,5,9] 中，金額 1,3 就無法被表示出來。

兩個貨币系統 (n,a) 和 (m,b) 是等價的，當且僅當對于任意非負整數 x，它要麼均可以被兩個貨币系統表出，要麼不能被其中任何一個表出。

現在網友們打算簡化一下貨币系統。

他們希望找到一個貨币系統 (m,b)，滿足 (m,b) 與原來的貨币系統 (n,a) 等價，且 m 盡可能的小。

他們希望你來協助完成這個艱巨的任務：找到最小的 m。

輸入格式

輸入檔案的第一行包含一個整數 T，表示資料的組數。

接下來按照如下格式分别給出 T 組資料。

每組資料的第一行包含一個正整數 n。

接下來一行包含 n 個由空格隔開的正整數 a[i]。

輸出格式

輸出檔案共有 T 行，對于每組資料，輸出一行一個正整數，表示所有與 (n,a) 等價的貨币系統 (m,b) 中，最小的 m。

資料範圍

1≤n≤100,

1≤a[i]≤25000,

1≤T≤20

#include <bits/stdc++.h>
using namespace std;
const int N=25010;
int n;
int a[N];
int f[N];
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=0;i<n;i++)cin>>a[i];
        sort(a,a+n);
        int res=0;
        memset(f,0,sizeof f);
        f[0]=1;
        for(int i=0;i<n;i++)
        {
            if(!f[a[i]])res++;
            for(int j=a[i];j<=a[n-1];j++)
                f[j]+=f[j-a[i]];
        }
        cout<<res<<endl;
    }
    return 0;
}