P8646 包子凑数

P8646 [蓝桥杯 2017 省 AB] 包子凑数

题目描述

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

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

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

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

输入格式

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

以下 $N$ 行每行包含一个整数 $A_i$。$(1\le A_i\le 100)$。

输出格式

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

输入输出样例 #1

输入 #1

2  
4  
5  

输出 #1

6

输入输出样例 #2

输入 #2

2  
4  
6   

输出 #2

INF

说明/提示

对于样例 $1$，凑不出的数目包括：$1,2,3,6,7,11$。

对于样例 $2$，所有奇数都凑不出来，所以有无限多个。

蓝桥杯 2017 省赛 A 组 H 题。

解析

核心问题一：什么时候会输出 INF（有无限个数凑不出）？

【思路解析】 题目问：给你 $N$ 种包子（比如一笼 4 个、一笼 6 个），你能不能凑出所有的数字？如果有无数个数字凑不出，就输出 INF。

这里直接用到数学上的一个著名定理：裴蜀定理。 用“人话”来说就是：如果这些数字的最大公约数（GCD）大于 1，那么它们能凑出来的数，永远只能是这个公约数的倍数！

• 举个通俗的例子： 假设你有两种蒸笼：一笼 4 个，一笼 6 个。 它们的最大公约数是 2。 你能凑出多少个包子？4, 6, 8, 10, 12, 14… 全都是偶数！ 那么奇数呢（1, 3, 5, 7, 9, 11…）？永远凑不出来！ 因为奇数有无限多个，所以此时凑不出的数有无限个，直接输出 INF。

• 反之： 如果一笼是 4 个，一笼是 5 个。 它们的最大公约数是 1（我们称之为“互质”）。 只要公约数是 1，数学上可以证明：凑不出的数字数量一定是有限的！（数字大到一定程度后，后面的所有数字都能凑出来）。

【代码对应】 这就是为什么我们在代码一开始，要用一个循环把所有数字的 gcd（最大公约数）求出来：

int g = a[0];
for(int i = 1; i < n; i++) {
    g = std::gcd(g, a[i]); 
}
if(g > 1) { cout << "INF\n"; return; }

---

核心问题二：如果凑不出的数是“有限的”，怎么找？为什么要开 100000 的数组？

【思路解析】 好，现在我们知道最大公约数是 1 了，凑不出的数是有限的。但问题是：这个“有限”到底有多大？我们需要算到多大的数字才算到头？

这里又要用到一个数学定理：赛瓦维斯特定理（麦乐鸡块定理 / 凑硬币定理）。 定理内容：如果两个数 $A$ 和 $B$ 互质，那么它们最大凑不出来的数字是 $A\times B-A-B$。

• 比如 4 和 5：最大凑不出的数字是 $4\times 5-4-5=11$。也就是说，12 及以上的数字绝对都能凑出来！

回到本题的数据范围： 题目说，每笼包子最多 $100$ 个（即 $A_i\le 100$）。 哪怕情况最极端，只有两个互质的数，比如 99 和 100，它们凑不出的最大数字也就是 $99\times 100-99-100=9701$。 也就是说，无论题目怎么给数据，超过 10000 左右的数字是绝对能凑出来的！

【代码对应】 为了绝对安全，我们把动态规划的数组上限 MAX_DP 设为 100000（10万）。10万以后的数不用管了，肯定都能凑出来。

---

核心问题三：怎么求具体有几个数凑不出？（完全背包问题）

【思路解析】 现在我们圈定了一个范围（1 到 100000），我们需要在这个范围内挨个判断：数字 $j$ 能不能凑出来？

这就变成了一个标准的**“完全背包问题”。因为每种蒸笼（每种物品）你可以买无限次**。

• 状态定义： 我们用一个数组 dp[j] 表示数字 $j$ 能不能凑出来。0 表示凑不出，1 表示能凑出。
• 初始状态（极其重要）： dp[0] = 1; 凑出 0 个包子是可能的（就是什么都不买）。这是一个“种子”，所有的数字都是从 0 开始加上去的。如果不把 0 设为 1，后面的数永远推导不出来。
• 状态转移过程： 假设我们现在手里有一种包子，一笼是 5 个（a[i] = 5）。 我们从小到大看每一个数字 $j$。如果我问你：12 个包子能凑出来吗？ 你只需要往前看 5 步：7 个包子能凑出来吗？
  • 如果 7 个包子能凑出来（dp[7] == 1），那我再加一笼 5 个的，绝对就能凑出 12 个！所以 dp[12] = 1。
  • 如果 7 个包子凑不出，那 12 目前也凑不出。

【代码对应】 这就是这两层循环的核心逻辑：

dp[0] = 1; // 种子：0个包子是可以凑出的
for (int i = 0; i < n; i++) // 遍历每一笼包子 a[i]
{
    for (int j = a[i]; j < MAX_DP; j++) // 从能买一笼 a[i] 的数字开始往后推
    {
        if (dp[j - a[i]] == 1) // 如果差一笼包子的那个数字能凑出来
        {
            dp[j] = 1;         // 那么加上这笼包子，当前的数字 j 也能凑出来！
        }
    }
}

代码

//
// Created by 23264 on 2026/2/22.
//
#include<bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
 
int n;
vector<int> a;
vector<int> dp;
constexpr int MAX_DP = 100005;
 
void solve()
{
    int g = a[0];
    for (int i = 1;i < n;i++)
    {
        g = gcd(g,a[i]);
    }
    if (g > 1)
    {
        cout << "INF" << "\n";
        return;
    }
    dp[0] = 1;
    for (int i = 0;i < n;i++)
    {
        for (int j = a[i];j < MAX_DP;j++)
        {
            if (dp[j - a[i]] == 1)
            {
                dp[j] = 1;
            }
        }
    }
 
    int ans = 0;
    for (int i = 1;i < MAX_DP;i++)
    {
        if (dp[i] == 0)
        {
            ans++;
        }
    }
    cout << ans << "\n";
}
 
int main()
{
    IOS;
    cin >> n;
    a.resize(n);
    dp.resize(MAX_DP,0);
    for (int i = 0;i < n;i++)
    {
        cin >> a[i];
    }
    solve();
}