Number of buns

Xiao Ming eats breakfast at a bun shop almost every morning. He found that the bun was paved with N kinds of steaming cages, of which the second type just fits Ai buns. Each type of steamer has many cages, which can be considered infinite.

Whenever a customer wants to buy X buns, the uncle who sells buns quickly picks up several cages of buns so that there happens to be X buns in all of them. For example, there are three steamers, which can hold 3, 4 and 5 buns. When the customer wants to buy 11 buns, the uncle will choose 2 cages 3 plus 1 cage 5 (or maybe 1 cage 3 plus 2 cages 4).

Sometimes, of course, Uncle Baozi can't figure out how many customers want to buy. For example, there are three kinds of steamers that can hold 4, 5 and 6 buns. When the customer wanted to buy seven buns, his uncle couldn't come up with them.

Xiao Ming wants to know how many kinds of buns Uncle can't come up with.

Enter a description
The first line contains an integer N ( 1 ≤ N ≤ 100 ) N(1 \leq N \leq100) N(1≤N≤100).

Following N N N rows contain an integer per row A i ( 1 ≤ A i ≤ 100 ) A_i(1 \leq A_i \leq 100) Ai​(1≤Ai​≤100).

Output Description
An integer represents the answer. If there is an infinite number, output INF.

Input and Output Samples
Example 1
input

2
4
5

output

6

Sample Description
Countless numbers include: 1, 2, 3, 6, 7, 11.

Example 2
input

2
4
6

output

INF

Sample Description
Not all odd numbers come together, so there are infinite numbers

thinking

• It looks familiar, feels a little vague, and then recalls the composition of the general solution of the system of linear equations in linear algebra, the extremely linear independent group, the base of vectors, the rank of matrices, etc. But I still have no clue.
• However, it is a little inspiration to find a maximally linear independent group of vectors, each of which can be represented by this maximally linear independent group.
• If I can find a few numbers in the number of buns given (as a "very irrelevant group") so that any number of buns can be represented by these numbers, then there are a limited number of buns that cannot be represented.
• So for this question, if you can find a "very unrelated group", you can output how many buns can't be compacted, otherwise you will output INF
• How does it mean "you can find very irrelevant groups"?
• The original problem can be converted into an equation solving problem, that is, the number of buns given as a factor, the number of buns per cage is unknown (natural number), and the number required by the customer is constant, that is, the number of buns per cage is constant. a 1 ∗ x 1 + a 2 ∗ x 2 + ⋯ + a n ∗ x n = b a_1*x_1+a_2*x_2+\dots+a_n*x_n=b a1 x1 +a2 x2 + +an xn =b where ( a 1 , a 2 , ... , a n ) (a_1,a_2,\dots,a_n) (a1, a2,..., an) is the number of buns per cage given. b b b is the number of buns requested by the customer. What we are asking for is ( x 1 , x 2 , ... , x n ) (x_1,x_2,\dots,x_n) (x1, x2,..., xn), the number of buns
• Then referring to other people's problems, I found a theorem that I don't know, so I don't have to be entangled in the "extremely irrelevant group" anymore. I use the following theorems to understand the problem more clearly
• Pei Shu Theorem: The combination of any two numbers must be a multiple of their greatest common divisor.
• Promotion: If n n The greatest common divisor of n numbers is k k k, then their combination is k k Multiple of k if k ≠ 1 k\not =1 k=1, there must be an infinite number that cannot be combined
• If the maximum common divisor of the number of buns per cage is not 1, the INF should be output
• If the number of buns given is reciprocal, that is, the maximum common divisor is 1, then it is known by the theorem that there are a finite number of buns that cannot be worked out and that the number of output buns should be
• However, the title does not say what the maximum number of buns the customer requests. Here you can only determine a general idea:
• Because if there are only two mutually prime numbers a , b a,b If a,b, then the upper limit for this "number that cannot be expressed" is u = ( a − 1 ) ∗ ( b − 1 ) − 1 u=(a-1)*(b-1)-1 u=(a−1)∗(b−1)−1
• I think it's good to use this idea to determine the upper bound: when there are more numbers, the upper bound gets smaller and the title data is limited A i A_i Ai is within 100, then 10,000 is a better upper limit (actually 10,000 is already larger than the original upper limit)
• Here we formally clear our mind and begin to solve problems
• Full Backpack (Dynamic Planning)
• d p dp dp array can be set to Boolean array, true representation can be compacted, false representation can not be compacted, the number of false statistics is the answer
• Initialization d p [ 0 ] [ 0 ] = 1 dp[0][0]=1 dp[0][0]=1 because 0 buns will come together
• State transfer equation i f ( j ≥ a [ i ] ) : d p [ i ] [ j ] = d p [ i − 1 ] [ j ] ∣ ∣ d p [ i ] [ j − a [ i ] ] ; if (j\geq a[i]):dp[i][j]=dp[i-1][j]||dp[i][j-a[i]]; if(j≥a[i]):dp[i][j]=dp[i−1][j]∣∣dp[i][j−a[i]]; e l s e : d p [ i ] [ j ] = d p [ i − 1 ] [ j ] ; else :dp[i][j]=dp[i-1][j]; else:dp[i][j]=dp[i−1][j];

The code is as follows

//Unoptimized Version
#include <iostream>
#include <vector>
using namespace std;

const int MAX_VAL = 10000;//upper bound

vector<int> a;//Array of buns
vector<vector<bool>> dp;//DP Array
int n;//Number of bun cages given

//Find the greatest common divisor of two numbers
int gcd(int m, int n) {
    if (n == 0) return m;
    return gcd(n, m % n);
}

int main() {
    scanf("%d", &n);
    int cd = 0;//Greatest common divisor
    int i = 0, j = 0;//Temporary variable
    a.resize(n);
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        cd = gcd(cd, a[i]);
    }
    if (cd == 1) {
        dp.resize(n + 1);
        for (i = 0; i <= n; i++) {
            dp[i].resize(MAX_VAL, false);
        }
        dp[0][0] = true;
        for (i = 1; i <= n; i++) {
            for (j = 0; j < MAX_VAL; j++) {
                dp[i][j] = dp[i - 1][j] ||
                           ((j >= a[i - 1]) ? dp[i][j - a[i - 1]] : false);
            }
        }
        int ans = 0;
        for (i = 0; i < MAX_VAL; i++) {
            if (!dp[n][i]) ans++;
        }
        printf("%d\n", ans);
    } else {
        printf("INF\n");
    }
    return 0;
}



//Optimized Version
#include <iostream>
#include <vector>
using namespace std;
const int MAX_VAL = 10000;
vector<int> a;
vector<bool> dp;
int n;

int gcd(int m, int n) {
    if (n == 0) return m;
    return gcd(n, m % n);
}

int main() {
    scanf("%d", &n);
    int cd = 0;
    int i = 0, j = 0;
    a.resize(n);
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        cd = gcd(cd, a[i]);
    }
    if (cd == 1) {
        dp.resize(MAX_VAL, false);
        dp[0] = true;
        for (i = 1; i <= n; i++) {
            for (j = 0; j < MAX_VAL; j++) {
            //Is this inner loop as if only 01 backpacks are reversed?
                if (j >= a[i - 1]) dp[j] = dp[j] || dp[j - a[i - 1]];
            }
        }
        int ans = 0;
        for (i = 0; i < MAX_VAL; i++) {
            if (!dp[i]) ans++;
        }
        printf("%d\n", ans);
    } else {
        printf("INF\n");
    }
    return 0;
}