Title Source: Blue Bridge Cup-2017

Xiao Ming eats breakfast at a bun shop almost every morning. This bun is 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 sells buns and chooses several cages 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.

input
The first line contains an integer N. (1 <= N <= 100)
The following N lines contain an integer Ai per line. (1 <= Ai <= 100)

output
The output line contains an integer representing the answer. If there is an infinite number, output INF.

Example

Input:

2
4
5

Output:

6

Input:

2
4
6

Output:

INF

The difficulty of this question is how to judge if there are infinite numbers that cannot be composed. The following is an infinite number of deductions. Readers who already know the cause can directly think of it as a question line by underlining it.

Take two examples, for example, where 4 and 5 cannot consist of only six: 1, 2, 3, 6, 7, 11. 4 and 6 cannot consist of 2 and all odd numbers.

Starting with the numbers 4 and 6, we can know when there are infinite numbers that cannot be composed: 6 and 4 are multiples of 2, so almost all multiples of 2 can be represented by 4 and 6, at which point all odd numbers cannot be represented. That is, if the maximum common factor of two numbers is not 1, the number they can make up is actually a multiple of the maximum common factor, for example, the number of 4 and 6 can make up a multiple of 2. So as long as you take any number that is not a multiple of 2, it must not be represented by 4 and 6.

If you look at the numbers 4 and 5, their maximum common factor is 1, can they make up all the numbers? We find that all even numbers except 1, 2, 3, 6, 7, 11 seem to be represented by multiples of 4. If a number cannot divide 4 completely, then we can set aside a part for 5. Take 10 for example, 10 is even but 10 cannot be divided by 4, 2*4=8, 3*4=12, and the difference between them is 4. At this point, we can use 2*5=10 to compensate for the intermediate interpolation 2, so that we can use a*4+b*5 to make up almost all even numbers. Similarly, a*5+b*4 can be used to form almost all odd numbers. Then x*4+y*5 can make up almost all the numbers, at which point there are only a few that can't be made up.

That is, no matter what kind of data we are given, if some of the numbers in them have a maximum common factor of not 1, then they are actually multiples of the maximum common factor, there must be an unrepresentable number in between.

To sum up, if the maximum common factor given to our numbers is 1, that is, they are mutually prime, then the number that cannot be formed is finite, and vice versa, infinite.

First, we need to write a function to determine if the input data is mutually homogeneous. Here we use the Euclidean algorithm, which is the rolling division.

If you don't know the algorithm, you can look at an example to see how it works, or click on a link to access it Euclidean algorithm-Baidu Encyclopedia.

If you need to find the greatest common divisor of two positive integers, 1997 and 615, the Euclidean algorithm does this:
1997 / 615 = 3 (remaining 152)
615/152 = 4 (remaining 7)
152/7 = 21 (remaining 5)
7/5 = 1 (remaining 2)
5/2 = 2 (remaining 1)
2/1 = 2 (remaining 0)
So far, the maximum common divisor is 1
Repeatedly divides by divisor and remainder. When the remainder is 0, divides the current formula by the greatest common divisor. Thus, the greatest common divisor 1 of 1997 and 615 is obtained.

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

Write a startup function to preprocess data

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int[] input = new int[n];
    for (int i = 0; i < n; i++)
        input[i] = scanner.nextInt();
    get(input);
}

The following is a code that you think is very easy to understand. It is very inefficient to execute (at least slowly, visually slow) and can be greatly optimized after understanding.

This code explanation will be explained using input data 245. First, a GCD is defined to indicate whether the input data is mutually homogeneous. Since each calculation refreshes the value of the gcd, the GCD will always be 1 only if all the data is mutually homogeneous. Using gcd, you can directly determine whether to output INF.

If you don't output an INF, which means you have a limited number of representations, then first create a list to store all the input data. Then create a res to hold the numbers that cannot be represented. First add all the data to the list using a for loop, such as 4,5. Then we set a threshold, iterate through all the numbers in the range, and detect whether they can be represented by the data in the list.

First, define a flag=false to indicate whether the currently processed number i can be composed of numbers in the list. If it does, let flag = true and add this number to the list. The way to deal with whether or not a number can be made up is to determine if it can be made up of itself. For example, when we determine the number 6, we first determine whether 0 and 6 are in the list, and then 1 and 5, 2 and 4, 3 and 3. As long as a set of judgments is successful, it means that numbers can be composed. In this topic, after traversing these four situations, no solution has been found, so 6 is not a number that can be formed. Conversely, if it can be formed, flag=true will end the cycle and add the value to the list to facilitate subsequent calculation. At the end of the loop, add 6 to res with flag=false. Until the entire loop is traversed, since we add all the numbers that can't be made up, we can simply output the size of the res. See the code for a detailed process.

public static void get(int[] input) {
    //gcd initial value
    int gcd = input[0];
    //Determine if all input data is mutually homogeneous
    for (int i = 0; i < input.length - 1; i++)
        gcd = gcd(gcd, input[i + 1]);
    //If not, output INF, otherwise enter
    if (gcd == 1) {
        //Used to store all the numbers that can be made up, which can be used later
        //Because list. Contains(4) && list. Contains(5), 4+5=9
        //So list.add(9)
        //The number that this quick-thinking judgment can make up
        List<Integer> list = new ArrayList<>();
        //Used to store numbers that cannot be composed
        List<Integer> res = new ArrayList<>();
        //Input data can naturally be composed, simply add
        for (int i = 0; i < input.length; i++)
            list.add(input[i]);
        //Traverse to threshold 10000
        for (int i = 1; i <= 10000; i++) {
            //identifier
            boolean flag = false;
            //flag only changes when it can be composed, and if it can, the loop stops, so add it here! flag's judgment
            for (int j = 0; j <= i / 2 && !flag; j++)
                //We don't think about the special value 0 here. In fact, when we judge 4, there is no 0, but 4 is real, so we add ||list directly. Contains condition
                if ((list.contains(j) && list.contains(i - j)) || list.contains(i)) {
                    //If i exists in the list, you do not need to add i anymore
                    if (!list.contains(i))
                        list.add(i);
                    //An identifier change that indicates the end of the loop or that the number can be composed
                    flag = true;
                }
            //Choose to add i to res based on the value of flag
            if (!flag)
                res.add(i);
        }
        //The size of the res is the number of digits that cannot be made up
        System.out.println(res.size());
    } else
        System.out.println("INF");
}

We find that using a list is really for the purpose of using his contains method, but such a large amount of time is consumed and it undoubtedly incurs a lot of time loss to decide whether or not to include each time. In fact, we can write a bool array and use the subscript as each number to determine whether or not it is composed. This way, list.contains(4) can be written as bool[4]. Similarly, the title does not allow us to give all the values that are not composable, so all we need to do is define a count counter, which adds one for every occurrence of a number that is not composable. This way the code will look like this (the rewritten part has been commented out)

public static void get(int[] input) {
    int gcd = input[0];
    for (int i = 0; i < input.length - 1; i++)
        gcd = gcd(gcd, input[i + 1]);
    //Define counters, no longer create res to collect non-composable numbers
    int count = 0;
    if (gcd == 1) {
        //Threshold is 10000, created to 10001 to take advantage of subscripts, defaults to false
        boolean[] isGet = new boolean[10001];
        //The input data can be composed, that is, true
        for (int i = 0; i < input.length; i++)
            isGet[input[i]] = true;
        //The front code does not take into account 0, which is taken into account here. It ensures that each value of the array is meaningful, as well as that such as 0 and 4 
        isGet[0] = true;
        for (int i = 1; i <= 10000; i++) {
            boolean flag = false;
            for (int j = 0; j <= i / 2 && !flag; j++)
                //The case of 0 has already been considered, so the condition has been removed and contains can be replaced by array subscripts as mentioned above
                if (isGet[j] && isGet[i - j])
                    //Change the subscript value to true while also changing the flag
                    isGet[i] = flag = true;
            if (!flag)
                count++;
        }
    }
    //Output statements can be integrated into one, but they can also be written without this, making them more readable if written separately from the if statement
    System.out.println(gcd == 1 ? count : "INF");
}

import java.util.Scanner;

public class bao_zi_cou_shu {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] input = new int[n];
        for (int i = 0; i < n; i++)
            input[i] = scanner.nextInt();
        get(input);
    }

    public static void get(int[] input) {
        int gcd = input[0];
        for (int i = 0; i < input.length - 1; i++)
            gcd = gcd(gcd, input[i + 1]);
        int count = 0;
        if (gcd == 1) {
            boolean[] isGet = new boolean[10001];
            for (int i = 0; i < input.length; i++)
                isGet[input[i]] = true;
            isGet[0] = true;
            for (int i = 1; i <= 10000; i++) {
                boolean flag = false;
                for (int j = 0; j <= i / 2 && !flag; j++)
                    if (isGet[j] && isGet[i - j])
                        isGet[i] = flag = true;
                if (!flag)
                    count++;
            }
        }
        System.out.println(gcd == 1 ? count : "INF");
    }

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

No execution time and memory consumption statistics for this topic