C :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char a[256*256];
int b[305];
int gcd(int a, int b){
if(a % b)return gcd(b,a%b);
else return b;
}

int cmp(const void *a, const void *b){
return (*(int*)a)-(*(int*)b);
}

int main()
{
    int n;
    while(scanf("%d",&n) != EOF){
        char ff = 0;
        int gys;
        for(int i = 1;i <= n; i++){
            scanf("%d",&b[i]);
            if(b[i] == 1)ff = 1;
        }
        gys = gcd(b[1],b[2]);
        for(int i = 3;i <= n; i++){
            gys = gcd(gys,b[i]);
        }
        if(ff || gys != 1){
            printf("0\n");
            continue;
        }
        memset(a,0,sizeof(a));
        a[0] = 1;
        qsort(b+1,n,sizeof(int),cmp);
        int mm = b[n]*b[n];
        int mi = b[1];
        for(int i = mi;i <= mm; i++){
            for(int j = 1;j <= n;j ++){
                if(i >= b[j]){
                    if(a[i-b[j]]==1){
                        a[i] = 1;
                    }
                }
            }
        }
        int kk = 0;
        for(int i = mm;i >= 1; i--){
            if(a[i]==0){
                kk=i;
                break;
            }
        }
        printf("%d\n",kk);
    }

    return 0;
}

C++ :

#include<iostream>
#include<algorithm>
using namespace std;
const int N(70000);
int n,a[15];
bool f[N];
//ifstream cin("nuggets.in");
//ofstream cout("nuggets.out");
int gcd(int x,int y)
{
    int z;
    for (z=x%y;z;x=y,y=z,z=x%y);
    return y;
}
bool possible()
{
    if (n==1) return false;
    int t=a[0];
    for (int i=1;i<n;i++) t=gcd(t,a[i]);
    if (t==1) return true;
    else return false;
}
void solve()
{
    fill(f,f+N,false);    
    for (int i=0;i<n;i++) f[a[i]]=true;
    for (int i=1;i<N;i++)
    {
        for (int j=0;j<n;j++)
            if (a[j]<=i)
                if (f[i-a[j]])
                {
                    f[i]=true;
                    break;
                }
    }
    for (int i=N-1;i>0;i--)
        if (!f[i])
        {
            cout<<i<<endl;
            break;
        }
}
int main()
{    
    while (cin>>n)
    {
        fill(f,f+N,0);        
        for (int i=0;i<n;i++) cin>>a[i];
        if (!possible()) cout<<0<<endl;
        else solve();
    }
    return 0;
}