[Blue Bridge Cup 2017 preliminary] buns make up

subject

Title Description
Xiao Ming has breakfast in a bun shop almost every morning . This bun shop has N Grow steamer , Among them the first i The kind of steamer can put Ai A steamed bun
Each kind of steamer has a lot of steamers , It can be thought of as an infinite cage .
Whenever a customer wants to buy X A steamed bun , Uncle will choose some steamed buns , So that these cages happen to have X A steamed bun .
Let's say there are 3 Grow steamer , You can put 3、4 and 5 A steamed bun . When customers want to buy 11 A bun , Uncle will choose 2 Cage 3 One more 1 Cage 5 One of the （ It is also possible to elect 1 Cage 3 One more 2 Cage 4 One of the ）.
Of course, sometimes uncle baozi can't figure out the quantity customers want to buy .
Let's say there are 3 Grow steamer , You can put 4、5 and 6 A steamed bun . And customers want to buy 7 A bun , Uncle can't make it out .
Xiao Ming wants to know how many kinds of numbers can't be found by Uncle baozi .
Input format
The first line contains an integer N.(1 <= N <= 100)
following N Each line contains an integer Ai.(1 <= Ai <= 100)
Output format
The output line contains an integer to represent the answer . If you can't figure out an infinite number , Output INF.
sample input Copy
2
4
5
sample output Copy
6
Data range and tips
For example , The uncountable number includes ：1, 2, 3, 6, 7, 11.

analysis ：

This problem needs to know a theorem , Euclidean theorem ： For not completely 0 The integer of a,b So there must be integers x,y bring gcd(x,y) = a * x + b * y.
So we can assume that a * x + b * y = d, To make the equation solvable , that d % gcd(a, b) = 0 It is inevitable , If gcd(a,b) = 1, that d Can divide any number , That is to say a,b this 2 Any number can be divided by numbers （ But there can't be negative numbers in it , So there are some numbers that cannot be summed up ）, On the contrary, we can't .
So the first step is to find the greatest common divisor of these numbers , If gcd = 1, Then how many numbers can't be summed up in the judgment , If gcd != 1, Then there must be countless kinds of numbers that can't be summed up , Direct output INF.

Reference code ：

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
#include <unordered_map>
#define LL long long
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define reps(i, a, b) for(int i = a; i < b; i++) 
#define pre(i, a, b) for(int i = b; i >= a; i--)
using namespace std;

const int N = 10010, M = 110;

int f[N];
int a[N];

int main()
{
    
	int n;
	cin >> n;
	
	int g = 0;
	rep(i, 1, n)
	{
    
		cin >> a[i];
		g = __gcd(g, a[i]);
	}
	
	if(g != 1) 
	{
    
		puts("INF");
		return 0;
	}
	
	rep(i, 1, n) f[a[i]] = 1;
	
	rep(i, 1, n)
		for(int j = 0; j + a[i]<= 10000; j++) //  Here to 10000 It's a little metaphysical （ mathematics , No ）
		{
    
			if(f[j]) f[j + a[i]] = 1;
		}
		
	int ans = 0;
	rep(i, 1, 10000)
		if(!f[i]) ans++;
	
	cout << ans << endl;
	return 0;
	
}