本文針對“包子湊數”問題，深入解析如何通過最大公約數（GCD）判斷無法組成的數目是否無限，并結合動態規劃高效求解有限情況下的具體數目。通過清晰的算法思路、代碼實現及示例詳解，揭秘數論與動態規劃在組合問題中的巧妙應用，幫助讀者掌握核心解題技巧。文章還包含復雜度分析與關鍵注意事項，適合算法學習者和編程愛好者閱讀。

題目描述

小明想知道包子鋪用給定的蒸籠規格能湊出多少種無法組成的包子數目。若無法組成的數目無限，輸出 INF。

輸入格式

• 第一行為整數 $N$（蒸籠種數）
• 接下來 $N$ 行每行一個整數 $A_i$（每種蒸籠的包子數）

輸出格式

• 無法湊出的數目個數，若無限則輸出 INF

問題分析

關鍵條件

若所有 $A_i$ 的最大公約數（GCD）不為 1，則無法組成的數目無限。例如，當所有數均為偶數時，無法組成任何奇數。

動態規劃思路

當 GCD 為 1 時，使用動態規劃判斷每個數是否能被組成：

• 定義 dp[i] 表示能否湊出 i 個包子。
• 狀態轉移：若存在某個 $A_j$ 使得 dp[i - A_j] 為真，則 dp[i] 為真。

解題步驟

1. 計算 GCD：若 GCD ≠ 1，直接輸出 INF。
2. 動態規劃求解：遍歷 1 到 100000，統計無法組成的數目。

代碼實現

#include<iostream>
#include<algorithm>
using namespace std;int N;
int num[110];
bool dp[100010];  // dp[i]表示能否組成i個包子// 計算最大公約數
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);
}int main() {cin >> N;int g = 0;  // 初始GCD為0for (int i = 1; i <= N; ++i) {cin >> num[i];g = gcd(g, num[i]);  // 更新GCD}// 若所有數的GCD不為1，輸出INFif (g != 1) {cout << "INF" << endl;return 0;}dp[0] = true;  // 0個包子可以湊出// 動態規劃填充數組for (int i = 1; i <= 100000; ++i) {for (int j = 1; j <= N; ++j) {if (i >= num[j] && dp[i - num[j]]) {dp[i] = true;  // 標記當前數目可湊}}}// 統計無法湊出的數目int res = 0;for (int i = 1; i <= 100000; ++i) {if (!dp[i]) ++res;}cout << res << endl;return 0;
}

復雜度分析

• 時間復雜度：$O(N\times M)$，其中 $M=10^5$ 為遍歷的最大數，$N$ 為蒸籠種數。
• 空間復雜度：$O(M)$，存儲動態規劃狀態。

示例解釋

樣例輸入1

2  
4  
5

輸出：6
解釋：無法湊出的數為 1, 2, 3, 6, 7, 11。

樣例輸入2

2  
4  
6

輸出：INF
解釋：所有奇數無法湊出，數目無限。

總結

本題結合數論（GCD判斷）與動態規劃，需注意：

1. 先通過 GCD 判斷是否為無限情況。
2. 動態規劃時需覆蓋足夠大的范圍以確保正確性。