题目一看，是个 组合问题，是完全背包问题的变形：有几个物品，每个物品无限个，每个物品选任意个，能否凑到某个重量。

但是，题目说会出现有无限个数被凑不出来的， 说明这些数的$gcd$不是1。

这里用到裴蜀定理 ，$任意两个数的组合必定是他们gcd的$倍数，同样可以推广到更多数：如果这些数的$gcd是d$，那么他们的组合是$d$的倍数，如果$d$不是1，那么必然有无限个数无法被组合出来。

$所以，要先写个欧几里得算法，两两求下gcd，看gcd是否大于1。$
$欧几里得算法：gcd(a,b)=gcd(b,a\%b) 。当余数为0时，当前算式的除数就是a和b的gcd。$

$那么，gcd为1呢？最大不能表示出来的数必定有个上界，因为两个数a,b（当gcd=1时），最大不能表示出来的$数是：$(a-1)(b-1)-1$。当数字更多的时候，这个上界必然更小（可选的数字变多了），而99和98是100内最大的$互质的数，所以这个上界选择10000。$

那么下面的事情就是看这么多数中有多少个不能被组合出来，回到了刚开始分析的完全背包问题：

1.状态定义:

$dp(i,j)表示前选i项物品任意个，重量为j，属性为能否达到重量j(true/false)$

2.状态转移：

$集合分析法：由最后不同的一步来划分集合，在重量为j的时候，第i$个物品选了几件。
$dp(i,j)=dp(i-1,j)||dp(i-1,j-w(i))||…||dp(i-1,j-k*w(i)) (k=j/w(i)) $

但是，完全背包问题有个特殊的地方：那就是 状态重叠 ：
$dp(i,j-w(i))是由dp(i-1,j-w(i))||dp(i-1,j-2 * w(i))…||dp(i-1,j-k *w(i))(k=j/w(i))$转移过来，仔细看上下两个式子就会发现$dp(i,j-w(i))的状态就是dp(i,j)后面一大部分。$

$所以最终方程为:dp(i,j)=dp(i-1,j)||dp(i,j-w(i))(w(i)\le j)$

3.初始化：

$dp(0,0)=true$ 0件物品，0重量的时候肯定是可以凑出来的。

4.递推顺序：

这里$i和j$依次正序枚举就好。

5.答案统计：

$dp(n,j)(0\le j \le 10000)中有多少个false。$

6.优化：

由于转移方程中当前状态只会用到前一行同一列的那个状态，以及前面才更新过的状态，因此状态数组可以压成一维:$dp(j)=dp(j)||dp(j-w(i))(j \ge w(i))$。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<stack>
#include<climits>
#define x first
#define y second
#define MP make_pair
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 100 + 5;
int n, a[N]; 
bool dp[N][10005];

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

int main(void){
    cin >> n;
    int d = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        d = gcd(d, a[i]);
    }
    memset(dp, 0, sizeof dp);
    dp[0][0] = true;
    if (d != 1) cout << "INF";
    else{
        for (int i = 1; i <= n; ++i){
            for (int j = 0; j <= 10000; ++j)
                dp[i][j] = dp[i - 1][j] || (j >= a[i] ? dp[i][j - a[i]] : false);
        }

        int ans = 0;
        for (int j = 0; j <= 10000; ++j)
            if (!dp[n][j]) ans++;
        cout << ans;
    }

    return 0;
}