1.题目引入：
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有 NN 种蒸笼，其中第 ii 种蒸笼恰好能放 A_i 个包子。每种蒸笼都有非常多笼，可以认为是无限笼。
每当有顾客想买 X个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有 X 个包子。比如一共有 3 种蒸笼，分别能放 3、4 和 5 个包子。当顾客想买 11 个包子时，大叔就会选 2 笼 3 个的再加 1 笼 5 个的（也可能选出 1 笼 3 个的再加 2 笼 4 个的）。
当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有 3 种蒸笼，分别能放 4、5 和 6 个包子。而顾客想买 7 个包子时，大叔就凑不出来了。
小明想知道一共有多少种数目是包子大叔凑不出来的。
输入描述
第一行包含一个整数 NN ( 100≤N≤100)。
以下 N 行每行包含一个整数 Ai (100≤Ai≤100)。
输出描述
一个整数代表答案。如果凑不出的数目有无限多个，输出 INF。
2.样例输出：
示例 1
输入
2 4 5输出
6样例说明
凑不出的数目包括：1, 2, 3, 6, 7, 11。
示例 2
输入
2 4 6输出
INF
思路：
这题是一个完全背包的问题：
数学结论：
两个数a,b（当gcd=1时）（gcd 应该知道吧，它是用来求最大公约数的即：欧几里德算法，相当于我们的辗转相除法）最大不能表示出来的数是：(a−1)(b−1)−1
,（大家可以验证一下，只要大于这个数的一定可以用a,b两个质数表示出来）根据数据范围，直接枚举到10000。有些小伙伴可能就要问了，我的0< n< 200 那我们的范围岂不就变成了：200 ^200；有没有这样想的，如果你这样想了先点个赞我们继续向下看。只有当两个数时它的范围是最大的，显然两个数能表示的范围我多个数所表示的范围自然更大了。大脑又短路了不是。
这里的状态定义也挺特殊的，不过很容易想到：
f[i][j]表示从前i个数中选，目标总质量为j,属性是能否达到j。
状态转移：按照第i个物品选的数量来进行划分：
f[i][j] == f[i−1][j]|f[i−1][j−w[i]]|f[i−1][j−2∗w[i]]|…|f[i−1][j−k∗w[i]];
（注意：因为是满足一项就说明可以装满，这里用到的是异或运算符）
完全背包的优化:
f[i][j−w[i]] = f[i−1][j−w[i]]|f[i−1][j−2∗w[i]]|f[i−1][j−3∗w[i]]|…|f[i−1][j−k∗w[i]];
优化：
f[i][j] == f[i−1][j]|f[i][j−w[i]];
到一维：
f[j]|=f[j−w[i]];
到这里我们发现他其实就是一个完全背包的板子题，具体操作如下：
3.代码如下：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e4+10,m=1e4;
int a[maxn],n;
bool f[maxn];
int gcd(int x,int y)
{
return y?gcd(y,x%y):x;
}
int main()
{
int q=0,ans=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
q=gcd(q,a[i]);
}
if(q!=1)
{
puts("INF");
return 0;
}
f[0]=1; // 确定边界，当背包没有空间时表示符合要求
for(int i=1;i<=n;i++)
{
for(int j=a[i];j<=m;j++)
{
f[j]|=f[j-a[i]];
}
}
for(int i=0;i<=m;i++)
{
if(!f[i])
{
ans++;
}
}
cout<<ans<<"\n";
return 0;
}