代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int M = 105 ;
using namespace std ;
inline int read() {
    char c = getchar() ; int x = 0 , w = 1 ;
    while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
    while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }
    return x*w ;
}

int n , a[M] , Ans ;
int p[M] , num ;
bool IsCan = true ;
inline void Clear() {
    Ans = 0 ; num = 0 ;
    memset(p , 0 , sizeof(p)) ;
    IsCan = false ;
}
void Dfs(int Goal , int t , int tot) {
    if(IsCan) return ;
    if(tot > Goal) return ;
    if(tot && Goal % tot == 0) {
        IsCan = true ;
        return ;
    }
    if(t < 1) return ;
    int upp = Goal / p[t] ;
    for(int i = 0 ; i <= upp ; i ++) {
        if(tot + i * p[t] > Goal) break ;
        Dfs(Goal , t - 1 , tot + i * p[t]) ;
        if(IsCan) return ;
    }
}
inline int Div1() {
    sort(a + 1 , a + n + 1) ;
    if(a[n] % a[1] == 0) printf("1\n") ;
    else printf("2\n") ;
}
inline int Div2() {
    sort(a + 1 , a + n + 1) ;
    p[++num] = a[1] ;
    if(a[2] % a[1] > 0) p[++num] = a[2] ;
    Dfs(a[3] , num , 0) ;
    if(!IsCan) p[++num] = a[3] ;
    printf("%d\n",num) ;
}
inline int Div3() {
    sort(a + 1 , a + n + 1) ;
    p[++num] = a[1] ;
    for(int i = 2 ; i <= n ; i ++) {
        IsCan = false ;
        Dfs(a[i] , num , 0) ;
        if(!IsCan) p[++num] = a[i] ;
    }
    printf("%d\n",num) ;
}
int main() {
//	freopen("money.in","r",stdin) ;
//	freopen("money.out","w",stdout) ;
    int T = read() ;
    while(T --) {
        Clear() ;
        n = read() ;
        for(int i = 1 ; i <= n ; i ++) a[i] = read() ;
        if(n == 2) Div1() ;
        else if(n == 3) Div2() ;
        else Div3() ;
    }
    return 0 ;
}

评测结果