打卡記錄

包子湊數（裴蜀定理 + DP）

根據裴蜀定理，存在 c = gcd(a, b) 使不定方程ax + by = c滿足條件，如果gcd(a, b) == 1即a與b互素的情況下，就會 ax + by = 1，由于為1可以構造后面的無窮數字，故得到結論當 gcd(a, b) == 1 時，才存在有限無法構造的數字情況。根據定理a， b最大無法構造的數字為 (a - 1)(b - 1) - 1，而后再采用 0-1 背包的算法思想解決。

import math
import sysn, m = int(input()), 10000
nums = [int(input()) for _ in range(n)]g = nums[0]
for num in nums:g = math.gcd(g, num)
if g != 1:print("INF")sys.exit(0)f = [0 for _ in range(m)]for i in range(n):f[nums[i]] = 1for j in range(nums[i] + 1, m):f[j] |= f[j - nums[i]]cnt = 0
for i in range(1, m):if f[i] == 0:cnt += 1print(cnt)