题目描述

推荐以下的题解：
作者： Mamba_ZJP
链接： https://www.acwing.com/solution/content/17888/

作者： 辰风
链接： https://www.acwing.com/solution/content/8980/

在数论中，裴蜀定理是一个关于最大公约数（或最大公约式）的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b(可以是多个数)和它们的最大公约数d:
ax + by = m

有解当且仅当m是d的倍数。裴蜀等式有解时必然有无穷多个整数解，每组解x、y都称为裴蜀数，可用辗转相除法求得。

特别来说，方程 ax + by = 1 有解当且仅当整数a和b互素。

对于本题公约数不是1的话，那么gcd的k倍无法表示所有的数

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

样例

import java.util.*;

public class Main {

    //99和98是100内最大的互质的数，所以这个上界选择10000。
    static final int N = 10010;
    static int[] a = new int[110];
    static boolean[][] f = new boolean[110][N];

    //算最大的公约数
    static int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();


        int d = 0;
        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
            d = gcd(d, a[i]);
        }

        if(d != 1){
           System.out.println("INF");
        }
        else {
            //0件物品，0重量的时候肯定是可以凑出来的。
            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++;

            System.out.println(res);
        }
    }

}