Buns make up the number----Euclide+dp

Title description:

Xiao Ming eats breakfast at a steamed bun shop almost every morning.He found that this steamed bun shop has N kinds of steamers, and the i-th steamer can hold Ai buns exactly.Each type of steamer has a very large number of cages, which can be considered as infinite cages.Whenever a customer wants to buy X steamed buns, the uncle who sells steamed buns will quickly select a number of steamed buns, so that there are exactly X steamed buns in these cages.For example, there are 3 types of steamers, which can hold 3, 4 and 5 buns respectively.When a customer wants to buy 11 buns, the uncle will choose 2 cages of 3 plus 1 cage of 5 (may also choose 1 cage of 3 plus 2 cages of 4).Of course, sometimes Uncle Baozi can't make up the quantity that customers want to buy anyway.For example, there are 3 types of steamers, which can hold 4, 5 and 6 buns respectively.And when the customer wanted to buy 7 buns, the uncle couldn't come out.
Xiao Ming wants to know how many kinds of numbers there are that Uncle Baozi can't come up with.
Input
----
The first line contains an integer N.(1 <= N <= 100)
Each of the following N lines contains an integer Ai.(1 <= Ai <= 100)
Output
----
An integer representing the answer.If there are infinite numbers that cannot be made up, output INF.
For example,
Input:
2
4
5
The program should output:
6
Another example,
Input:
2
> 4
6
The program should output:
INF
Example explanation:
For example 1, the numbers that cannot be made up include: 1, 2, 3, 6, 7, 11.
For example 2, all odd numbers cannot be made up, so there are infinitely many.
Resource convention:
Peak memory consumption (including virtual machine) < 256M
CPU consumption < 1000ms
Please output strictly as required, do not superfluous print something like: "Please enter..."redundant content.
Note:
The main function needs to return 0;
Only use the ANSI C/ANSI C++ standard;
Do not call special functions that depend on the compilation environment or operating system.
All dependent functions must be explicitly #include
Common header files cannot be omitted through project settings.
When submitting your program, take care to select the desired language type and compiler type.

Thinking:

1. Under what circumstances will INF be output?

For example, the above case: 2 4 6, as long as it is an odd number, he can't make it up, because the least common divisor of these three numbers is 2, and only the least common divisor is 1 can it be made up

2. How to determine which ones cannot be assembled?

You can set a dp array, loop:

dp[0] = 1;for (int i = 0; i < n; i++){for (int j = 0; j + arr[i] < 100001; j++){if (dp[j])dp[j + arr[i]] = 1;}}

If you can figure it out, dp[i]=1

Code:

#include using namespace std;bool judge(int x, int y){int t;while(y>0){t=x%y;x=y;y=t;}if(x==1)return true;return false;}int a[110],n;bool dp[10010];int main(){scanf("%d",&n);for(int i=0; i