題目描述

標題：包子湊數(shù)小明幾乎每天早晨都會在一家包子鋪吃早餐。他發(fā)現(xiàn)這家包子鋪有N種蒸籠，其中第i種蒸籠恰好能放Ai個包子。每種蒸籠都有非常多籠，可以認為是無限籠。每當有顧客想買X個包子，賣包子的大叔就會迅速選出若干籠包子來，使得這若干籠中恰好一共有X個包子。比如一共有3種蒸籠，分別能放3、4和5個包子。當顧客想買11個包子時，大叔就會選2籠3個的再加1籠5個的（也可能選出1籠3個的再加2籠4個的）。當然有時包子大叔無論如何也湊不出顧客想買的數(shù)量。比如一共有3種蒸籠，分別能放4、5和6個包子。而顧客想買7個包子時，大叔就湊不出來了。小明想知道一共有多少種數(shù)目是包子大叔湊不出來的。輸入 ---- 第一行包含一個整數(shù)N。(1 <= N <= 100) 以下N行每行包含一個整數(shù)Ai。(1 <= Ai <= 100) 輸出 ---- 一個整數(shù)代表答案。如果湊不出的數(shù)目有無限多個，輸出INF。例如， 輸入： 2 4 5 程序應該輸出： 6 再例如， 輸入： 2 4 6 程序應該輸出： INF樣例解釋： 對于樣例1，湊不出的數(shù)目包括：1, 2, 3, 6, 7, 11。 對于樣例2，所有奇數(shù)都湊不出來，所以有無限多個。 資源約定： 峰值內(nèi)存消耗（含虛擬機） < 256M CPU消耗 < 1000ms請嚴格按要求輸出，不要畫蛇添足地打印類似：“請您輸入...” 的多余內(nèi)容。所有代碼放在同一個源文件中，調(diào)試通過后，拷貝提交該源碼。 不要使用package語句。不要使用jdk1.7及以上版本的特性。 主類的名字必須是：Main，否則按無效代碼處理。 提交程序時，注意選擇所期望的語言類型和編譯器類型。

思路分析

代碼實現(xiàn)

package com.atguigu.TEST;import java.util.Scanner;class Main{public static int n,g;public static int a[]=new int[101];public static boolean f[]=new boolean[10000];//a*b-a+bpublic static int gcd(int a,int b){if(b==0) return a;return gcd(b,a%b);}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);n = scanner.nextInt();f[0]=true;for (int i = 1; i <= n; i++) {a[i]=scanner.nextInt();if(i==1) g=a[i];//初始化最大公約數(shù)else g=gcd(a[i],g);for (int j = 0; j+a[i]<10000; j++) {if(f[j])f[j+a[i]]=true;}}if(g!=1){System.out.println("INF");return;}//統(tǒng)計個數(shù)int ans=0;for (int i = 0; i < 10000; i++) {if(!f[i]){ans++; // System.out.println(ans);}}System.out.println(ans);}}

總結

以上是生活随笔為你收集整理的2017蓝桥杯省赛---java---B---8(包子凑数)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。