題目：

時間限制: 1Sec 內存限制: 128MB 提交: 1049 解決: 365

題目描述

小明幾乎每天早晨都會在一家包子鋪吃早餐。他發現這家包子鋪有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的偶數都可寫成兩個質數之和。但是我沒想出來，后來問了會長，才知道要用拓展歐幾里得判是否所有數互質，好的吧。特殊情況：不構成的數為INF時：充分條件是：包子的數目最大公約數都不為1，（即包子的數目都為一個數的倍數，這個數不是1）{歐幾里得擴展變形}，但數據挺弱的，不考慮特判也能過。

AC代碼：

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int inf=0x3f3f3f3f; const int M=1e6+10; int t,ans; int a[110],dp[M]; int gcd(int x,int y){return y==0?x:gcd(y,x%y); } int main(){scanf("%d",&t);scanf("%d",&a[1]);ans=a[1];for(int i=2;i<=t;i++){scanf("%d",&a[i]);ans=gcd(ans,a[i]);}if(ans!=1) printf("INF\n");else{memset(dp,0,sizeof(dp));dp[0]=1;for(int i=1;i<=t;i++){for(int j=0;j<M;j++){if(dp[j])dp[j+a[i]]=1;}}int num=0;for(int i=1;i<M;i++)if(!dp[i])num++;printf("%d\n",num);}return 0; }

總結

以上是生活随笔為你收集整理的题目 1886: [蓝桥杯][2017年第八届真题]包子凑数（欧几里得+完全背包）的全部內容，希望文章能夠幫你解決所遇到的問題。

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