包子凑数

解法:数论 + 完全背包

参考大佬的详解:
https://www.acwing.com/solution/content/17888/

#include<cstdio>
#include<algorithm>
using namespace std;
#define N 10010

int a[110];
bool f[110][N];

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

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

        d = gcd(d,a[i]);
    }

    if(d != 1)  puts("INF");
    else
    {
        f[0][0] = true;
        for(int i = 1;i <= n;i ++)
            for(int j = 0;j < N;j ++)
            {
                f[i][j] = f[i-1][j];
                if(j >= a[i])   f[i][j] |= f[i][j-a[i]];
            }

        int res = 0;
        for(int i = 0;i < N;i ++)
            if(!f[n][i])
                res ++;

        printf("%d\n",res);
    }

    return 0;
}

优化版

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 10010;

int a[110];
bool f[N];

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

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

    if (d != 1) puts("INF");
    else
    {
        f[0] = true;
        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 = 0; i < N; i ++ )
            if (!f[i])
                res ++ ;

        printf("%d\n", res);
    }

    return 0;
}