Acwing 1226 包子凑数

Content

小明几乎每天早晨都会在一家包子铺吃早餐。

他发现这家包子铺有 N种蒸笼，其中第 i种蒸笼恰好能放 Ai个包子。

每种蒸笼都有非常多笼，可以认为是无限笼。

每当有顾客想买 X个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有 X个包子。

比如一共有 3种蒸笼，分别能放 3、4和 5个包子。

当顾客想买 11个包子时，大叔就会选 2笼 3个的再加 1笼 5个的（也可能选出 1笼 3个的再加 2笼 4个的）。

当然有时包子大叔无论如何也凑不出顾客想买的数量。

比如一共有 3种蒸笼，分别能放 4、5和 6个包子。

而顾客想买 7 个包子时，大叔就凑不出来了。

小明想知道一共有多少种数目是包子大叔凑不出来的。

Input

第一行包含一个整数 N。

接下来 N 行，每行包含一个整数 Ai。

Output

输出一个整数代表答案。

如果凑不出的数目有无限多个，输出INF。

Solution

本质上是一个完全背包问题但是不同的是，它要求的是有多少种方案不存在。

如果所有数A1~An的公约数d大于1，那么所有不能被d整除的数都凑不出来，即INF

如果所有数A1~An的公约数d等于1，那么如果一个数很大，它必能凑出，即凑不出的数目为有限个

如果两个数a,b互质，那么他们凑不出来的最大的数为(a-1)*(b-1)-1。因此由数，我们可以估计出凑不出来的最大的数的上界为10000。

完全背包的变种+数论，代码如下：

#include<iostream>

using namespace std;

const int N = 10010;

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

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

    int d = a[1];
    for(int i=2;i<=n;++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++;
        }
        cout<<res<<endl;

    }
    return 0;

}