（2017）第八届蓝桥杯大赛个人赛省赛（软件类） C/C++ 大学A组 题解（第八题包子凑数）

第八题
题目
标题：包子凑数
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼，其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼，可以认为是无限笼。
每当有顾客想买X个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼，分别能放3、4和5个包子。当顾客想买11个包子时，大叔就会选2笼3个的再加1笼5个的（也可能选出1笼3个的再加2笼4个的）。
当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼，分别能放4、5和6个包子。而顾客想买7个包子时，大叔就凑不出来了。
小明想知道一共有多少种数目是包子大叔凑不出来的。
输入

第一行包含一个整数N。(1 以下N行每行包含一个整数Ai。(1 输出

一个整数代表答案。如果凑不出的数目有无限多个，输出INF。
例如，
输入：
2
4
5
程序应该输出：
6
再例如，
输入：
2
4
6
程序应该输出：
INF
样例解释：
对于样例1，凑不出的数目包括：1, 2, 3, 6, 7, 11。
对于样例2，所有奇数都凑不出来，所以有无限多个。
资源约定：
峰值内存消耗（含虚拟机） CPU消耗 请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
注意：
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include
不能通过工程设置而省略常用头文件。
提交程序时，注意选择所期望的语言类型和编译器类型。

第一种做法
分析
这道题如果要直接分析计算有多少个数无法被凑出来，似乎非常难。

那么能不能求出哪些数是无法被凑出来的呢很难。

但是哪些数能被凑出来是可以通过给定的数去用程序硬凑的。

这样，我们就可以去判断一个数能不能被凑出来了。

那我们就先实现一个吧。

那么这个数可以被凑出来要符合哪些条件呢/p>

1.这个数是给定的n个数之一。

2.这个数减去给定的n个数中的其中一个之后，依然可以被凑出来。

第1条显然成立，第2条我们稍作思考也会发现是对的，而且这两条包含了所有的情况。

当然，这种做法无法解决凑不出来的数是否无限。

代码及运行结果

还有一个问题就是，在这段代码中，我们默认只要判断到1000就足矣。但事实果真如此吗/p>

现在我们来着手解决这些问题。

第二种解法
分析
先考虑时间复杂度的问题。

我们会发现在从1计算到1000的过程中，每一个数都只考虑比它小的数的情况，不需要考虑比它大的数的情况。那么，我们在之前既然已经解决了这些比它小的数的情况，何不把它们记下来呢样对于每一个数，我们最多就只需要执行n次判断了。

那么这个时候我们再来考虑判断的范围。题目限制1s，也就是1e8次运算。那么每个数最多执行n次的情况下，保险起见我们也可以算到5e5个数。虽然我们无法确定这个范围是否足够，但是比1000就要保险得多。

代码及运行结果

之所以被称为记忆化搜索，是因为它在搜索的过程中记录了所有的结果。

这样做的好处是，如果每次搜索都是基于前面搜索的结果得出的话，效率就会被大大提高。

实际上，到目前为止，我们已经不用再往下研究了，因为这个程序足以让我们获得满分。当然，在比赛当中，如果你有充裕的时间，往下想也是理所应当的。

第八题的拓展
作为拓展内容，下面的内容会涉及到比较多的算法及数学知识。

第三种做法的正确性
首先我们来探究在给定的数最大公约数为1的情况下无法凑出的数是否是有限的。

根据上面的讲解：如果一个数可以被凑出来，那么它肯定是给定的数或者一个可以凑出来的数加上一个给定的数。

同理，如果一个数不可以被凑出来，那么它减去一个给定的数也是不能被凑出来的。

那么我们就会发现，不可以被凑出来的数在最稀疏的情况下也应该隔x出现一次（x为一个给定的数）。

我们来考虑这个性质的本质：对于x来说，所有的数其实都可以分成x类：根据对x的余数来分。

只要某类里的一个数被凑出来，那么这类数中无法被凑出来的数就一定是有限的。

这种划分出来的类被称为x的完全剩余系。

那么我们只需要考虑模x=0,1,2,3……x-1的数能不能凑出来就可以了。

很明显，如果模x=1可以被凑出来，其它就一定能被凑出来，所以我们只需要考虑这一种情况。

那么也就是说，我们考虑的是这些数凑出一个数减去若干个x能否等于1。

现在我们来学习一个新知识：裴蜀定理

以上摘自维基百科

如果你擅长离散数学，那么你会发现裴蜀定理在整环上不证自明：在主理想环中，a和b的最大公约元被定义为理想aA + bA的生成元。

现在我们假设x以外的n-1个数为$y_1$