判断是否有无限个凑不出的数

(两个质因子凑不出的数)买不到的数

https://www.acwing.com/solution/content/259736/

相似题
https://www.acwing.com/solution/content/261548/

import java.util.*;

public class Main {
    static final int N = 110, M = 10010;
    static int[][] f = new int[N][M];
    static int[] a = new int[N];
    static int n;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

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

        if (d != 1) {
            System.out.println("INF");
        } else {
            int ans = 0;
            f[0][0] = 1;//方案数初始化
            for (int i = 1; i <= n; i++)
                for (int j = 0; j < M; j++) {
                    f[i][j] = f[i - 1][j];
                    if (j >= a[i])
                        f[i][j] += f[i][j - a[i]];
                }

            //最后再进行统计，如果在上面统计会出现重复计算
            for (int j = 0; j < M; j++)
                if (f[n][j] == 0) ans ++;

            System.out.println(ans);
        }
    }

    static int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }
}

import java.util.*;

public class Main {
    static final int N = 110, M = 10010;
    static int[] f = new int[M];
    static int[] a = new int[N];
    static int n;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

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

        if (d != 1) {
            System.out.println("INF");
        } else {
            int ans = 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 j = 0; j < M; j++)
                if (f[j] == 0) ans ++;

            System.out.println(ans);
        }
    }

    static int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }
}