第八届蓝桥杯包子凑数

第八届蓝桥杯包子凑数问题：

    考察知识点：1.扩张欧几里得（ax + by = gcd(a,b)）

                        2.完全背包

/**
 * 
 */
package com.huat.lanqiao8;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author Administrator 2018年3月6日
 * @功能说明:第八届蓝桥杯包子凑数标题：包子凑数 小明几乎每天早晨都会在一家包子铺吃早餐。
 * 他发现这家包子铺有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
 * @version: 此程序用到的思想就是扩展欧几里得+完全背包
 */
public class NO_8 {

	public static int gcd(int a, int b) {
		int rem;
		while (b > 0) {
			rem = a % b;
			a = b;
			b = rem;
		}
		return a;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int i, j;
		int[] bk = new int[10000];
		int[] data = new int[n];

		for (i = 0; i < n; i++) {
			data[i] = sc.nextInt();
		}

		int g = data[0];
		for (i = 1; i < n; i++) {
			g = gcd(g, data[i]); // 求最大公约数
		}
		/**
		 * 如果最大公约数
		 */
		if (g != 1) {
			System.out.println("INF");
		} else {
			bk[0] = 1;
			for (i = 0; i < n; i++) {

				/**
				 * 按照每一笼来求，例如:4，5两笼包子，则首先只要是4的倍数都可以凑齐
				 * 然后i=1时，则可以凑齐5，9，10，13.。。。。
				 */
				for (j = 0; j + data[i] < 10000; j++) {
					if (bk[j] == 1) {
						bk[j + data[i]] = 1;
					}
				}
			}

			int ans = 0;
			for (i = 9999; i >= 0; i--) {
				if (bk[i] == 0)
					ans++;
			}

			System.out.println(ans);
		}
		sc.close();
	}
}