题意描述

在网友的国度中共有 $n$ 种不同面额的货币，第 $i$ 种货币的面额为 $a[i]$，你可以假设每一种货币都有无穷多张。

为了方便，我们把货币种数为 $n$、面额数组为 $a[1..n]$ 的货币系统记作 $(n,a)$

在一个完善的货币系统中，每一个非负整数的金额 $x$ 都应该可以被表示出，即对每一个非负整数 $x$，都存在 $n$ 个非负整数 $t[i]$ 满足 $a[i] \times 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$。

Input & Output ‘s examples

Input ‘s eg

2
4
3 19 10 6
5
11 29 13 19 17

Output ‘s eg

2
5

样例解释

在第一组数据中，货币系统 $(2,[3,10])$ 和给出的货币系统 $(n,a)$ 等价，并可以验证不存在 $m < 2$ 的等价的货币系统，因此答案为 $2$。

在第二组数据中，可以验证不存在 $m < n$ 的等价的货币系统，因此答案为 $5$。

数据范围和约定

对于$100\%$的数据，$1≤T≤20$,$n,a[i]≥1$。

分析

第一眼看到这题只想到了某凯的疑惑……

但当我们多读了几遍题后，就能提取出以下信息

一个货币系统是由n种不同的面额货币组成的。

如果这两个货币系统是等价的，那么对于一个数，它要么都可以被两个货币系统表示出来，要么不能被任何一个表示出来。

每一次询问，都会给我们一套货币系统，我们可以删掉其中的任意面额。但要求删掉该面额后的货币系统与原系统等价。即被删除的面额必须能用其他的面额表示出来

问该系统中最少需留下多少纸币。

还不懂吗？那我们来看一下样例。

在样例$3$ , $19$ , $10$ , $6$中，$3\times3 + 10 = 19$，即$19$可以被$3$张$3$元和$1$张$10$元表示出来。

同时，$6$也可以被$2$张$3$元表示出来。因此，$19$与$6$都可以被筛掉。

所以我们利用埃氏筛的思想，先建立一个数组$flag$，用其下标来记录这个钱数是否可以被表示出来。

筛到最后再跑一边$flag$，看一下货币系统之中还有几个无法凑出的钱数。这些无法凑出的钱数与原货币系统的交集就是最后的答案。

Code[Accepted]

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

#define ll long long
#define M 50001
#define N 201

using namespace std;

int t;
int n;
int a[N];   //原数组
int flag[M];
/*flag为筛选数组，0表示无法凑出，1表示可以凑出，2表示原来就有*/

int ans;

void start(){   //初始化变量
    ans = 0;
    memset(a , 0 , sizeof(a));
    memset(flag , 0 , sizeof(flag));
}//多测不清空，爆零两行泪

int main(){
    cin >> t;
    for(int qwq = 1; qwq <= t; qwq ++){
        start();
        cin >> n;
        for(int i = 1; i <= n; i ++){
            cin >> a[i];
            flag[a[i]] = 2;     //原来有的，就标2
        }
        sort(a + 1 , a + 1 + n);        //先排序，方便求解
        for(int i = 1; i <= a[n]; i ++){    
            if(flag[i] > 0){    //如果钱数i可以被凑出来，那么i + 其他可以被凑出来的货币也可以被凑出来
                for(int j = 1; j <= n; j ++){
                    if(a[j] + i <= a[n]){
                        flag[a[j] + i] = 1; //能凑出来，就标1
                    }
                    else{
                        break;
                    }
                }
            }
        }
        for(int i = 1; i <= a[n]; i ++){
            if(flag[i] == 2){       //看到最后还有哪些货币无法替代
                ans ++;
            } 
        }
        cout << ans << endl;
    }
    return 0;
}
//Written By Payphone-X