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满足∑i1NkiAiX \sum_{i1}^{N} k_i A_i Xi1∑NkiAiX每种蒸笼都能重复选所以这是一个完全背包问题。先求所有蒸笼容量的最大公约数ggcd(A1,A2,…,AN)g \gcd(A_1, A_2, \dots, A_N)ggcd(A1,A2,…,AN)按它分两种情况。g≠1g \ne 1g1能凑出的数一定是ggg的倍数不是ggg倍数的数就永远凑不出这样的数有无穷多个输出INF。样例 2 的 4、6 就是如此gcd(4,6)2\gcd(4, 6) 2gcd(4,6)2所有奇数都凑不出。g1g 1g1这时凑不出的数只有有限个赛瓦维斯特定理。Ai≤100A_i \le 100Ai≤100取上界M100×10010000M 100 \times 100 10000M100×10010000超过MMM的数都能凑出所以在这个范围内统计就够了。以样例4 5为例下图是 dp 数组被逐种蒸笼点亮的过程三行依次为初始、加入容量 4、加入容量 5 之后深绿的格子是本次新点亮的在[0,M)[0, M)[0,M)上做完全背包用dp标记能凑出的数dp[0] True。对每种蒸笼容量aaajjj从aaa正序遍历到M−1M-1M−1dp[j]dp[j]∨dp[j−a] dp[j] dp[j] \lor dp[j - a]dp[j]dp[j]∨dp[j−a]正序遍历保证同一种蒸笼能用多次。遍历结束后统计dp里False的个数即可。代码实现importmath nint(input())a[int(input())for_inrange(n)]M100*100# Ai 100取 10000 足够g0forxina:gmath.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是蒸笼种数M10000M 10000M10000。空间复杂度O(M)O(M)O(M)一个长度为MMM的布尔数组。 
长河君 · 2026/10/15 19:33:43 · 阅读 1.2k 98.包子凑数（数论+完全背包）
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满足∑i1NkiAiX \sum_{i1}^{N} k_i A_i Xi1∑NkiAiX每种蒸笼都能重复选所以这是一个完全背包问题。先求所有蒸笼容量的最大公约数ggcd(A1,A2,…,AN)g \gcd(A_1, A_2, \dots, A_N)ggcd(A1,A2,…,AN)按它分两种情况。g≠1g \ne 1g1能凑出的数一定是ggg的倍数不是ggg倍数的数就永远凑不出这样的数有无穷多个输出INF。样例 2 的 4、6 就是如此gcd(4,6)2\gcd(4, 6) 2gcd(4,6)2所有奇数都凑不出。g1g 1g1这时凑不出的数只有有限个赛瓦维斯特定理。Ai≤100A_i \le 100Ai≤100取上界M100×10010000M 100 \times 100 10000M100×10010000超过MMM的数都能凑出所以在这个范围内统计就够了。以样例4 5为例下图是 dp 数组被逐种蒸笼点亮的过程三行依次为初始、加入容量 4、加入容量 5 之后深绿的格子是本次新点亮的在[0,M)[0, M)[0,M)上做完全背包用dp标记能凑出的数dp[0] True。对每种蒸笼容量aaajjj从aaa正序遍历到M−1M-1M−1dp[j]dp[j]∨dp[j−a] dp[j] dp[j] \lor dp[j - a]dp[j]dp[j]∨dp[j−a]正序遍历保证同一种蒸笼能用多次。遍历结束后统计dp里False的个数即可。代码实现importmath nint(input())a[int(input())for_inrange(n)]M100*100# Ai 100取 10000 足够g0forxina:gmath.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是蒸笼种数M10000M 10000M10000。空间复杂度O(M)O(M)O(M)一个长度为MMM的布尔数组。