你好呀，我是灰小猿，一個超會寫bug的程式猿！

歡迎大家關注我的專欄“每日藍橋”，該專欄的主要作用是和大家分享近幾年藍橋杯省賽及決賽等真題，決議其中存在的演算法思想、資料結構等內容，幫助大家學習到更多的知識和技術！

標題：包子湊數

小明幾乎每天早晨都會在一-家包子鋪吃早餐.他發現這家包子鋪有N種蒸籠,其中第i種蒸

籠恰好能放Ai個包子.每種蒸籠都有非常多籠，可以認為是無限籠.

每當有顧客想買X個包子，賣包子的大叔就會迅速選出若干籠包子來，使得這若干籠中恰

好一共有X個包子.比如一共有3種蒸籠，分別能放3. 4和5個包子.當顧客想買11個

包子時,大叔就會選2籠3個的再加1籠5個的(也可能選出1籠3個的再加2籠4個的).

當然有時包子大叔無論如何也湊不出顧客想買的數量.比如一-共有3種蒸籠，分別能放4.

5和6個包子.而顧客想買7個包子時，大叔就湊不出來了.

小明想知道一共有多少種數目是包子大叔湊不出來的，

輸入

第- -行包含-一個整數N. (1<=N<= 100)

以下N行每行包含-一個整數Ai. (1<= Ai<= 100)

輸出

一個整數代表答案.如果湊不出的數目有無限多個，輸出INF.

例如,

輸人:

2

4

5

程式應該輸出:

6

再例如輸入：

2

4

6

程式應該輸出：

INF

樣例解釋

對于樣例1，湊不出的數目包括：1, 2, 3, 6, 7, 11，
對于樣例2，所有奇數都湊不出來，所以有無限多個，

【資源約定】

峰值記憶體消耗(含虛擬機) < 256M

CPU消耗< 1000ms

請嚴格按要求輸出，不要畫蛇添足地列印類似: " 請您輸人..”的多余內容.

所有代碼放在同一個源檔案中，除錯通過后，拷貝提交該原始碼.

不要使用package陳述句，不要使用jdk1.7及以上版本的特性.

主類的名字必須是: Main, 否則按無效代碼處理.

提交程式時，注意選擇所期望的語言型別和編譯器型別.

解題思路：

本題在求解上用到的思想與完全背包問題類似，同時在2013年也有一道類似的題目叫“買不到的數目”，像了解的小伙伴可以看我的這篇文章“【每日藍橋】9、一三年省賽Java組真題“買不到的數目””，

本題的求解首先需要搞清楚一個定理：互為質數的兩個數a和b，最大不能組成的數n=a*b-a-b

如果兩個數不互質，則最大不能組成的數無上限，

所以在本題求解的時候，我們知道包子數最大是100，所以最大不能組成的數最大也是100*100-100-100=9800

那么我們其實可以判斷輸入的數是否互質，如果互質（即最大公約數等于1）則例舉出0~10000以內所有能湊出的數，然后再得出不能湊出的數的個數，

如果輸入的數不互質（即最大公約數不等于1），那么說明最大不能湊成的數無上限，直接輸出INT即可，

對于如何找出0~10000以內所有能湊出的數，可以使用類似于動態規劃的思想，利用布爾型陣列將能湊出的數標記為true，不能則記為false，最后統計標記為false的數的個數即可，

答案原始碼：

package 一七年省賽真題;

import java.util.Scanner;


public class Year2017_Bt8 {

	static int ans;
	static int g;
	static boolean []arr = new boolean[10100];	//記錄0~10000中的數是否能被湊出,在這里將陣列長度定義的長一點
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int [] a = new int[N];
		arr[0] = true;//表示0是可以湊出來的，即一個都不買
		for (int i = 0; i < N; i++) {
			a[i] = scanner.nextInt();
			if (i==0) g = a[i];
			g = gcd(g,a[i]);//求最大公約數
			
			for (int j = 0; j < 10000; j++) {
				//如果當前的數是可以被湊出來的，那么這個數加上剛剛輸入的數也一定是可以被湊出來的，
				if (arr[j]) arr[j+a[i]]=true;
			}
		}
		//如果說所有的數輸入完之后，得到的最大公約數不是1，說明不互質
		//如果數不互質，則有無限多個數湊不出來
		if (g!=1) {
			System.out.println("INF");
			return ;
		}
		
		//找出0~10000之內所有不能被湊出的數
		for (int i = 0; i < 10000; i++) {
			if(!arr[i]) {
				ans++;
			}
		}
		System.out.println(ans);	

	}
	
	/**
	 * 求兩個數的最大公約數
	 * */
	private static int gcd(int a, int b) {
		if(b==0) return a;
		return gcd(b, a%b);
	}



}