標題：包子湊數

小明幾乎每天早晨都會在一家包子鋪吃早餐。他發現這家包子鋪有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，否則按無效代碼處理。
提交程序時，注意選擇所期望的語言類型和編譯器類型。

解析：這個問題只要用桶的方式暴力就可以了，只要是a[i]的倍數必定是能夠取到的，題目稍微難一點的地方就在于INF情況的判斷，這會涉及到拓展歐幾里得算法，這是對歐幾里得算法（輾轉相除法）的一個拓展：對于不全為0的兩個數a, b，如果我們用gec(a, b)表示a, b的最大公約數，那么必然存在整數對x, y，使得gad(a, b) = ax + by。也就是說如果a[i]這些數只要最大公倍數不是1，那么就不會出現INF。

import java.util.Scanner;public class Main2 {static int n;static int[] a = new int[10005]; static boolean[] vis; static int sum = 0;public static void main(String[] args) {Scanner in = new Scanner(System.in);n = in.nextInt();vis = new boolean[10005];for (int i = 0; i < n; i++) {a[i] = in.nextInt();}int g = a[0];for (int i = 1; i < n; i++) {g = gcd(g, a[i]);}/*** 拓展歐幾里得：對于不全為0的兩個數a,b，* 如果我們用gcd(a,b)表示a,b的最大公約數，* 那么必然存在整數對x,y, 使得gad(a,b) = ax+by* */if (g != 1) {System.out.println("INF");} else {vis[0] = true;for (int i = 0; i < n; i++) {for (int j = 0; j+a[i] < 10005; j++) {if (vis[j] == true) {vis[j + a[i]] = true;}}}for (int i = 0; i <= 10000-1; i++) {if (vis[i] == false) {sum++;}}System.out.println(sum);}}private static int gcd(int a, int b) {// TODO Auto-generated method stubif (b == 0) {return a;}return gcd(b, a%b);} }

總結

以上是生活随笔為你收集整理的蓝桥杯第八届省赛JAVA真题----包子凑数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。