企业官网建设流程全解析

98. 包子凑数（数论+完全背包）

2017年蓝桥杯省赛 - 包子凑数（困难）

标签：2017省赛数论完全背包

题目描述

小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有NNN种蒸笼，其中第iii种蒸笼恰好能放AiA_iAi​个包子。每种蒸笼都有非常多笼，可以认为是无限笼。

每当有顾客想买XXX个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有XXX个包子。比如一共有 3 种蒸笼，分别能放 3、4 和 5 个包子。当顾客想买 11 个包子时，大叔就会选 2 笼 3 个的再加 1 笼 5 个的（也可能选出 1 笼 3 个的再加 2 笼 4 个的）。

当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有 3 种蒸笼，分别能放 4、5 和 6 个包子。而顾客想买 7 个包子时，大叔就凑不出来了。

小明想知道一共有多少种数目是包子大叔凑不出来的。

输入描述

第一行包含一个整数NNN(1≤N≤100)(1 \le N \le 100)(1≤N≤100)。

以下NNN行每行包含一个整数AiA_iAi​(1≤Ai≤100)(1 \le A_i \le 100)(1≤Ai​≤100)。

输出描述

一个整数代表答案。如果凑不出的数目有无限多个，输出 INF。

输入输出样例

示例 1：

输入

2 4 5

输出

6

示例 2：

输入

2 4 6

输出

INF

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

解题思路

凑XXX个包子，等价于找一组非负整数k1,k2,…,kNk_1, k_2, \dots, k_Nk1​,k2​,…,kN​满足

∑i=1NkiAi=X \sum_{i=1}^{N} k_i A_i = Xi=1∑N​ki​Ai​=X

每种蒸笼都能重复选，所以这是一个完全背包问题。先求所有蒸笼容量的最大公约数g=gcd⁡(A1,A2,…,AN)g = \gcd(A_1, A_2, \dots, A_N)g=gcd(A1​,A2​,…,AN​)，按它分两种情况。

g≠1g \ne 1g=1：能凑出的数一定是ggg的倍数，不是ggg倍数的数就永远凑不出，这样的数有无穷多个，输出INF。样例 2 的 4、6 就是如此，gcd⁡(4,6)=2\gcd(4, 6) = 2gcd(4,6)=2，所有奇数都凑不出。

g=1g = 1g=1：这时凑不出的数只有有限个（赛瓦维斯特定理）。Ai≤100A_i \le 100Ai​≤100，取上界M=100×100=10000M = 100 \times 100 = 10000M=100×100=10000，超过MMM的数都能凑出，所以在这个范围内统计就够了。

以样例4 5为例，下图是 dp 数组被逐种蒸笼点亮的过程，三行依次为初始、加入容量 4、加入容量 5 之后，深绿的格子是本次新点亮的：

在[0,M)[0, M)[0,M)上做完全背包，用dp标记能凑出的数，dp[0] = True。对每种蒸笼容量aaa，jjj从aaa正序遍历到M−1M-1M−1：

dp[j]=dp[j]∨dp[j−a] dp[j] = dp[j] \lor dp[j - a]dp[j]=dp[j]∨dp[j−a]

正序遍历保证同一种蒸笼能用多次。遍历结束后统计dp里False的个数即可。

代码实现

importmath n=int(input())a=[int(input())for_inrange(n)]M=100*100# Ai <= 100，取 10000 足够g=0forxina:g=math.gcd(g,x)ifg!=1:print("INF")# 不是 g 的倍数的数都凑不出，有无穷多个else:dp=[False]*M dp[0]=Trueforxina:forjinrange(x,M):# 正序遍历，每种蒸笼可用多次dp[j]=dp[j]ordp[j-x]print(M-sum(dp))

复杂度分析

• 时间复杂度：O(NM)O(NM)O(NM)，NNN是蒸笼种数，M=10000M = 10000M=10000。
• 空间复杂度：O(M)O(M)O(M)，一个长度为MMM的布尔数组。