P8646 [蓝桥杯 2017 省 AB] 包子凑数 题解
题目传送门
P8646 [蓝桥杯 2017 省 AB] 包子凑数
一、题目描述
小明发现包子铺有N种蒸笼，每种能放A_i个包子（无限供应）。问有多少个正整数X无法被这些蒸笼数量的组合表示出来。若无限多个则输出INF。
二、题目分析
这是一个典型的数论+动态规划问题。需要解决两个关键点：
- 判断无法表示的数字是否有无限多个
- 有限情况下统计具体无法表示的数字个数
三、问题思考
算法分析
本题需要结合数论中的裴蜀定理和动态规划来解决。
前置知识：裴蜀定理
对于任意整数a,b，存在整数x,y使得ax+by=gcd(a,b)。推广到多个数：
- 当所有数的gcd=1时，只有有限多个数无法表示
- 当gcd>1时，所有不被gcd整除的数都无法表示（无限多个）
四、动态规划思路
a. 状态表示
f[j]表示数字j能否被表示（true/false）
b. 初始化
f[0] = true（0个包子总是可以表示）
c. 状态转移
对于每个蒸笼数量a[i]，从a[i]开始更新：
if(f[j - a[i]]) f[j] = true;
d. 最终结果
统计所有f[j]==false的j的个数
五、代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 1e4 + 10; // N是蒸笼种类上限，M是DP数组大小
int n;
int a[N];// 计算最大公约数
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);
}bool f[M]; // DP数组int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n;for (int i = 1; i <= n; i ++) cin >> a[i];// 计算所有数的gcdint g = a[1];for (int i = 2; i <= n; i ++) {g = gcd(g, a[i]);}// 根据gcd判断是否有无限解if (g != 1) {cout << "INF";return 0;}// DP过程f[0] = true; // 初始化for (int i = 1; i <= n; i ++) { // 遍历每种蒸笼for (int j = a[i]; j < M; j ++) { // 更新DP数组if(f[j - a[i]]) f[j] = true;}}// 统计结果int res = 0;for (int i = 1; i < M; i ++)if (!f[i]) res ++;cout << res;return 0;
}
六、重点细节
- DP数组大小M：需要足够大（1e4）以确保能覆盖所有可能的解
- 状态转移顺序：必须正向更新，避免重复计算
- 初始化：
f[0]=true是正确计算的基础 - gcd计算：必须先判断gcd，避免无效的DP计算
七、复杂度分析
- 时间复杂度：O(N*M)，其中N≤100，M=1e4
- 空间复杂度：O(M)
八、总结
本题巧妙结合了数论和动态规划：
- 使用裴蜀定理判断解的有限性
- 通过完全背包式的DP统计具体解
- 代码简洁高效，体现了算法设计的精妙
关键点在于理解数论原理并将其与动态规划相结合，这也是算法竞赛中常见的解题思路。
- List item