题目描述

这道题与《买不到的数目》 类似，这里贴出《买不到的数目》的题解 (๑′ᴗ‵๑)

比较《买不到的数目》由两个数求最大凑不出的个数，变成了n个数凑不出来的数，本质是换汤不换药的，《买不到的数目》的数据保证有解，而《包子凑数》的数据不保证有解，可能有无限个凑不出的数，需要我们考虑。

这里我们需要知道：如果n个数的最大公因数是1，那么 这n个数的线性组合，p * a0 + q * a1 + … + k * an 它有一个最大凑不出的数，大于这个数之后的所有数都可以被凑出。(裴蜀定理的推广)，那么如果最大公因数不是1，就一定有无限个凑不出的数。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=10000;
const int M=110;
int dp[N];
int n,a[M];
int gcd(int a,int b){//辗转相除法求最大公因数
    int temp;
    temp=max(a,b);
    b=min(a,b);
    a=temp;
    int r=a%b;
    while(r!=0){
        a=b;
        b=r;
        r=a%b;

    }

    return b;
}
int main(){

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

    }
    int d=a[0];
    for(int i=0;i<n;i++){
        d=gcd(d,a[i]);//两两比较查看他们之间的最大公因数    
    }
    if(d!=1){//看最大公因数是否为1 
        printf("INF");
        return 0;
    }

    dp[0]=1;

    for(int num=0;num<=N;num++){

        for(int i=0;i<n;i++){

            if(dp[num-a[i]]==1&&num-a[i]>=0){

                dp[num]=1;
            }
        }
    }


    int sum=0;
    for(int i=1;i<=N-1;i++){
        if(!dp[i]){
            sum++;

        }
    }
    printf("%d",sum);


    return 0;
}