AcWing 1226. 包子凑数

//1:两个数的gcd>1则有无限多个凑不出来,gcd==1则有有限个,对n个数同理
//2:两个互质的数最大凑不出来的数是(a-1)*(b-1)-1
//3:本题只考虑用100以内的n个数来凑,若这n个数含2个互质的数,则最大凑不出来的数<=10000,若不含,需要在100以内找到两两有公约数,且最大公约数为1的n个数
//又每个数可由几个质数的乘积得到,考虑用2 3 5得到 2*3 3*5 2*5这三个数两两不互质,且最大公约数为1,
//此时可把2*3和3*5加起来,得到3*7,与2*5互质,则2*3 3*5 2*5凑不出来的最大公约数<=10000
//考虑2 3 5 7得到2*3*5 3*5*7 5*7*2 2*3*7这时3*5*7已经>100,故这种情况不用考虑
//但是难证明出对n个最大公约数为1的数的最大凑不出来的数为哪个式子
//但对本题来说,取10000的经验值就行,即n个最大公约数为1从100内取的数的凑不出来的数在10000内考虑就行
#include <iostream>
using namespace std;
const int N=1e4+10;
int n;
int f[N];
int a[110];

int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}

int main()
{
    cin>>n;
    int d=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        d=gcd(d,a[i]);
    }

    if(d!=1/*d可能为负数,我不理解*/)puts("INF");
    else
    {
        f[0]=1;
        for(int i=1;i<=n;i++)
            for(int j=a[i];j<N;j++)
                f[j]|=f[j-a[i]];

        int res=0;
        for(int i=1;i<N;i++)res+=!f[i];
        cout<<res;
    }
}