包子湊數

輸入輸出樣例

示例 1

輸入

2
4
5

輸出

6

樣例說明

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

示例 2

輸入

2
4
6

輸出

INF

樣例說明

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

運行限制

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

---

最大公約數

最大公約數：Greatest Common Divisor,GCD,指兩個或多個整數共有約數中的最大值。

計算方法：

1. 質因數分解法：將各數分解為質因數，取共有質因數的最小冪次乘積。

   例如，求36和48的GCD：

   36=2^2 * 3^2,48=24 * 3^1

   GCD=2^2*31=12

2. 輾轉相除法（歐幾里得算法）：基于定理 gcd (a,b)=gcd (b,a mod b)，迭代至余數為零。

   例如，求 1071 和 462 的 GCD：

   1071 ÷ 462 = 2（余 147）→ gcd (462,147)

   462 ÷ 147 = 3（余 21）→ gcd (147,21)

   147 ÷ 21 = 7（余 0）→ GCD 為 21

裴蜀定理

1. 定理內容：對于多個整數，若其GCD為d，則它們線性組合的所有可能結果均為d的倍數。
2. 無限不可湊數判定：若所有整數的GCD大于1，則只能湊出d的倍數，此時就有無限多 無法湊出的數目，如GCD=2，那么所有的奇數都無法湊出。
3. 有限不可湊數判定：若GCD為1，則存在一個最大不可湊數M，超過M的所有數均可被湊出，

解題步驟

1. 首先輸入n和數組A
2. 情況一：若數組A中包含1，那么說明任何數都能湊，打印0.
3. 情況二：GCD!=1，則說明有無數個無法湊出的數，打印INF。
4. 情況三：GCD==1，則進入動態規劃步驟。

import math
def main():n = int(input())A = [[int(input())] for _ in range(n)]if 1 in A:print("0")returng = A[0]for a in A:g = math.gcd(a,g)if g != 1 :print("INF")returnelse :maxSize = 10000dp = [False] * (maxSize + 1)dp[0] = Truefor i in range(1, maxSize+1):if dp[i]:for a in A:if i+a < maxSize+1:dp[i+a] = Trueresult = 0for i in dp:if i == False:result += 1print(result)returnif __name__ == "__main__":main()