包子湊數

題目描述

小明幾乎每天早晨都會在一家包子鋪吃早餐。他發現這家包子鋪有?NN?種蒸籠，其中第?ii?種蒸籠恰好能放?AiAi??個包子。每種蒸籠都有非常多籠，可以認為是無限籠。

每當有顧客想買?XX?個包子，賣包子的大叔就會迅速選出若干籠包子來，使得這若干籠中恰好一共有?XX?個包子。比如一共有 3 種蒸籠，分別能放 3、4 和 5 個包子。當顧客想買 11 個包子時，大叔就會選 2 籠 3 個的再加 1 籠 5 個的（也可能選出 1 籠 3 個的再加 2 籠 4 個的）。

當然有時包子大叔無論如何也湊不出顧客想買的數量。比如一共有 3 種蒸籠，分別能放 4、5 和 6 個包子。而顧客想買 7 個包子時，大叔就湊不出來了。

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

輸入描述

第一行包含一個整數?NN?(1≤N≤1001≤N≤100)。

以下 N 行每行包含一個整數?AiAi??(1≤Ai≤1001≤Ai?≤100)。

輸出描述

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

輸入輸出樣例

示例 1

輸入

2
4
5

輸出

6

樣例說明

湊不出的數目包括：1, 2, 3, 6, 7, 11。

示例 2

輸入

2
4
6

輸出

INF

樣例說明

所有奇數都湊不出來，所以有無限多個

運行限制

• 最大運行時間：1s
• 最大運行內存: 256M

總通過次數: 8165??|??總提交次數: 9840??|??通過率: 83%

難度: 困難???標簽: 2017, 裴蜀定理, 省賽, 動態規劃

問題分析：包子湊數（裴蜀定理 + 動態規劃）

核心算法思路

1. ??裴蜀定理應用??：

   • 若所有蒸籠容量?Ai??的最大公約數?g=1，則存在無限多個無法湊出的數（輸出?INF）
   • 若?g=1，則無法湊出的數是有限的（需動態規劃統計）。

2. ??動態規劃（完全背包）??：

   • ??狀態定義??：dp[j] = true?表示能湊出?j?個包子。
   • ??初始化??：dp[0] = true（0 個包子不需要任何蒸籠）
   • ??狀態轉移??：

     for (每種蒸籠容量 a[i]) for (j = a[i]; j <= MAX; j++) dp[j] = dp[j] || dp[j - a[i]];

   • ??統計結果??：遍歷?dp[1..MAX]，計數?dp[j] = false?的數量

算法步驟

1. ??計算最大公約數??：

   • 初始化?g=A0?，遍歷?g=gcd(g,Ai?)。
   • 若?g=1，輸出?INF?并結束。

2. ??動態規劃求解??：

   • 設背包容量?MAX = 10000（因?Ai?≤100，最大不可湊數?<1002）
   • 對每種蒸籠容量更新?dp?數組。

3. ??統計無法湊出的數量??：

   • 遍歷?dp[1..MAX]，統計?false?的個數。

---

C++ 代碼實現

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;// 計算最大公約數
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);
}int main() {const int MAX = 10000;  // 背包最大容量int n;cin >> n;vector<int> a(n);vector<bool> dp(MAX + 1, false);  // dp數組初始化// 輸入并計算最大公約數int g = 0;for (int i = 0; i < n; i++) {cin >> a[i];g = (i == 0) ? a[i] : gcd(g, a[i]);}// 檢查最大公約數if (g != 1) {cout << "INF" << endl;return 0;}// 動態規劃（完全背包）dp[0] = true;  // 初始化：0個包子可湊出for (int i = 0; i < n; i++) {for (int j = a[i]; j <= MAX; j++) {if (dp[j - a[i]]) dp[j] = true;  // 狀態轉移}}// 統計無法湊出的數量int count = 0;for (int i = 1; i <= MAX; i++) {if (!dp[i]) count++;}cout << count << endl;return 0;
}

代碼解析

1. ??最大公約數計算??：

   • 使用遞歸實現輾轉相除法，時間復雜度?O(log(min(Ai?)))

2. ??動態規劃核心??：

   • ??空間優化??：使用一維?dp?數組，避免二維空間開銷
   • ??完全背包邏輯??：每種蒸籠無限使用，內層循環正序更新（區別于01背包的逆序）

3. ??邊界與效率??：

   • ??背包容量??：MAX=10000?的設定基于裴蜀定理（Ai?≤100?時最大不可湊數?<1002）
   • ??時間復雜度??：O(N×MAX)，滿足?N≤100、MAX=104，1秒內可完成

---

示例驗證

• ??輸入?[4, 5]??：
  • g=gcd(4,5)=1，動態規劃后統計得無法湊出?{1,2,3,6,7,11}，輸出?6。
• ??輸入?[4, 6]??：
  • g=gcd(4,6)=2=1，直接輸出?INF