洛谷 B3836 [GESP202303 二级] 百鸡问题

推荐洛谷GESP专题 全部实战题

洛谷同号 欢迎关注

恩师：hnjzsyjyj

一、题目介绍：从经典趣题到编程实践

1.1 题目背景

"百鸡问题" 是中国古代著名的数学趣题，最早出自《张丘建算经》。原题大意是："公鸡 5 文钱 1 只，母鸡 3 文钱 1 只，小鸡 3 只 1 文钱。用 100 文钱买 100 只鸡，问公鸡、母鸡、小鸡各买多少只？" 这道题因蕴含不定方程的求解思想而流传千古。

洛谷 B3836 是 GESP（编程能力等级认证）2023 年 3 月二级考试的真题，它在经典百鸡问题的基础上进行了改编，保留了核心的数学逻辑，同时调整了参数设置，更适合作为编程入门级的练习题。

1.2 题目描述

题目可以简化为：

• 现有三种物品，设购买数量分别为 i、j、k（均为非负整数）
• 已知五个参数 x、y、z、n、m
• 需满足两个条件：
  1. 数量关系：i + j + z×k = m
  2. 花费关系：x×i + y×j + k = n
• 要求计算并输出满足条件的购买方案总数

简单来说，就是要找出所有可能的 (i,j,k) 组合，使它们同时满足上述两个方程，其中 i、j、k 都不能是负数。

1.3 输入输出格式

• 输入：五个整数 x、y、z、n、m（通过空格分隔）
• 输出：一个整数，表示满足条件的方案总数

1.4 示例说明

以示例输入2 3 2 10 10为例：

• 我们需要找到非负整数 i、j、k 满足：
  1. i + j + 2k = 10（数量关系）
  2. 2i + 3j + k = 10（花费关系）
• 求解过程：
  • 由第一个方程得：i + j = 10 - 2k → k 的可能取值范围是 0~5（因为 2k≤10）
  • 代入第二个方程：2i + 3j = 10 - k
  • 当 k=4 时：i + j = 2，2i + 3j = 6 → 解得 i=0，j=2（均为非负整数，有效）
  • 其他 k 值计算后均出现负数解，故有效方案只有 1 种
• 输出结果：1

二、解题思路：枚举法破解不定方程

2.1 核心数学原理

这道题本质上是求解不定方程组的非负整数解。不定方程是指未知数数量多于方程数量的方程或方程组，通常有无数解，但在本题中由于变量的非负整数限制和参数约束，解的数量是有限的。

对于这类问题，最直观有效的方法是枚举法（也叫穷举法）：通过循环遍历可能的变量值，逐一验证是否满足所有条件，从而找出所有有效解。

2.2 变量关系分析

根据题目给出的两个方程：

1. i + j + z×k = m → 可变形为：k = (m - i - j) /z
2. x×i + y×j + k = n

从这两个方程可以得出关键结论：

• k 的值由 i 和 j 决定（k = (m - i - j) /z）
• k 必须是非负整数，因此 (m - i - j) 必须是 z 的倍数且结果非负
• 计算出 k 后，需要验证是否满足第二个方程

2.3 枚举范围确定

要枚举 i 和 j 的可能值，首先需要确定它们的合理范围：

• i 的范围：0 ≤ i ≤ m（因为 i 是非负整数，且 i ≤ m，否则 i + j + z×k 会超过 m）
• j 的范围：0 ≤ j ≤ m - i（因为 i + j ≤ m，否则 (m - i - j) 会是负数，导致 k 为负）

这样的范围设置既能覆盖所有可能的有效解，又能避免不必要的计算。

2.4 解题步骤总结

1. 输入 x、y、z、n、m 五个参数
2. 初始化计数器 ans 为 0（用于统计有效方案）
3. 外层循环遍历 i 的可能值（0 到 m）
4. 内层循环遍历 j 的可能值（0 到 m-i）
5. 对每一组 (i,j)，计算 (m-i-j)：
   • 若 (m-i-j) 不是 z 的倍数，跳过
   • 计算 k = (m-i-j)/z
   • 若 k 是非负整数且满足 x×i + y×j + k = n，则计数器加 1
6. 循环结束后，输出计数器的值

三、代码解析：逐行理解程序逻辑

下面我们来详细分析用户提供的代码，看看它是如何实现上述解题思路的：

cpp

运行

#include<bits/stdc++.h>
using namespace std;
int x,y,z,n,m,ans; 
int main() {
	cin>>x>>y>>z>>n>>m;
	for(int i=0;i<=m;i++){
		for(int j=0;j<=m-i;j++){
			if(x*i+y*j+(m-i-j)/z==n&&(m-i-j)%z==0)ans++;
		}
	}
	cout<<ans;
	return 0;
}

3.1 头文件与命名空间

cpp

运行

#include<bits/stdc++.h>
using namespace std;

• #include<bits/stdc++.h>：这是 C++ 的万能头文件，包含了几乎所有常用的标准库，可以简化代码编写
• using namespace std;：使用标准命名空间，这样我们可以直接使用cin、cout等标准库函数，而不必写成std::cin、std::cout

3.2 全局变量定义

cpp

运行

int x,y,z,n,m,ans; 

定义了 6 个整数变量：

• x、y：前两种物品的单价
• z：第三种物品的数量系数
• n：总花费
• m：总数量参数
• ans：计数器，用于统计有效方案的数量（全局变量默认初始值为 0）

3.3 主函数入口

cpp

运行

int main() {
    // 程序逻辑
    return 0;
}

main()函数是程序的入口，所有代码都在其中执行。

3.4 输入参数

cpp

运行

cin>>x>>y>>z>>n>>m;

通过cin从输入设备（通常是键盘）读取 5 个整数，分别存入 x、y、z、n、m 变量中。

3.5 外层循环（枚举 i 的值）

cpp

运行

for(int i=0;i<=m;i++){
    // 内层循环和判断条件
}

• 这是一个for循环，用于遍历 i 的所有可能值
• 初始条件：i=0（从购买 0 个第一种物品开始）
• 循环条件：i<=m（i 的最大值为 m）
• 迭代操作：i++（每次循环后 i 的值加 1）

3.6 内层循环（枚举 j 的值）

cpp

运行

for(int j=0;j<=m-i;j++){
    // 判断条件
}

• 这是嵌套在 i 循环内部的另一个for循环，用于遍历 j 的所有可能值
• 初始条件：j=0（从购买 0 个第二种物品开始）
• 循环条件：j<=m-i（确保 i+j 不超过 m，避免 k 为负数）
• 迭代操作：j++（每次循环后 j 的值加 1）

3.7 条件判断与计数

cpp

运行

if(x*i+y*j+(m-i-j)/z==n&&(m-i-j)%z==0)ans++;

这是整个程序的核心判断条件，包含两个关键检查：

1. (m-i-j)%z==0：检查 (m-i-j) 是否能被 z 整除，确保 k 是整数
2. x*i+y*j+(m-i-j)/z==n：计算 k 的值并检查是否满足花费关系

如果两个条件都满足，说明这是一个有效的购买方案，计数器ans的值加 1。

3.8 输出结果

cpp

运行

cout<<ans;

循环结束后，通过cout输出计数器ans的值，即有效方案的总数。

四、代码执行过程演示

为了更直观地理解代码的执行过程，我们以示例输入2 3 2 10 10为例，分步演示程序的运行：

1. 初始状态：x=2, y=3, z=2, n=10, m=10, ans=0

2. 外层循环 i=0：

   • 内层循环 j 的范围：0~10（因为 m-i=10）
   • j=0：
     • m-i-j=10-0-0=10
     • 10%2=0（满足整除条件）
     • k=10/2=5
     • 检查花费：20 + 30 + 5 = 5 ≠ 10（不满足，ans 不变）
   • j=1：
     • m-i-j=9 → 9%2=1（不满足整除条件，跳过）
   • j=2：
     • m-i-j=8 → 8%2=0 → k=4
     • 花费：0 + 6 + 4 = 10（满足条件，ans=1）
   • ...（后续 j 值计算均不满足条件）

3. 外层循环 i=1 到 10：

   • 依次计算各 i 值下 j 的可能取值
   • 经过计算，这些组合均不满足两个条件，ans 保持为 1

4. 循环结束：输出 ans 的值 1，与预期结果一致

通过这个过程可以看出，代码通过嵌套循环遍历了所有可能的 i 和 j 值，逐一检查条件，最终统计出有效方案的数量。

五、易错点分析：这些坑要注意

5.1 循环范围设置错误

最常见的错误是循环范围设置不当，主要有两种情况：

• 错误地将 i 的范围设置为i < m而不是i <= m，导致漏掉 i=m 的情况
• 错误地将 j 的范围设置为j <= m而不是j <= m-i，增加了不必要的计算，甚至可能导致 k 为负数

正确的范围设置是确保程序正确性和效率的关键。

5.2 整除判断遗漏

忘记检查(m-i-j)%z == 0这个条件，直接计算 k 的值，会导致 k 不是整数的情况被算作有效方案，从而得到错误结果。

例如当 (m-i-j) 不能被 z 整除时，(m-i-j)/z 会自动取整（如 5/2=2），但这其实是不符合题意的。

5.3 变量名混淆

由于题目中有多个参数（x、y、z、n、m），初学者容易在条件判断时混淆变量名，例如把x*i + y*j写成x*j + y*i，或者把 n 和 m 弄混。

解决这个问题的方法是给变量起更有意义的名字（虽然示例代码用了简写），或者在写代码时反复核对题目中的公式。

5.4 数据类型与溢出问题

虽然本题的输入范围不会导致溢出，但在处理更大数值时，需要注意 int 类型的取值范围限制。如果 m 的值非常大，i 和 j 的乘积可能超过 int 的最大值（2147483647），导致溢出错误。

解决方法是根据题目数据范围选择合适的数据类型，如 long long。

5.5 计数器初始化问题

如果将 ans 定义在 main 函数内部而忘记初始化，会导致 ans 的初始值是随机的，最终统计结果出错。

示例代码将 ans 定义为全局变量（默认初始值为 0），或者也可以在定义时显式初始化：int ans = 0;

六、优化方向：让代码更高效

6.1 缩小枚举范围

示例代码中的枚举范围是正确的，但还可以进一步优化：

• 对于 i，除了 i <= m，还可以根据花费条件 x*i <= n，得到 i <= n/x
• 同理，对于 j，除了 j <= m-i，还可以根据 yj <= n-xi，得到 j <= (n-x*i)/y

这样可以减少不必要的循环次数，提高程序效率：

cpp

运行

for(int i=0;i<=m && i<=n/x;i++){
    for(int j=0;j<=m-i && j<=(n-x*i)/y;j++){
        // 判断条件
    }
}

6.2 提前计算 k 并检查非负性

虽然示例代码的逻辑是正确的，但可以增加对 k 非负性的检查，使逻辑更清晰：

cpp

运行

int remain = m - i - j;
if(remain < 0) continue; // k为负数，跳过
if(remain % z != 0) continue;
int k = remain / z;
if(x*i + y*j + k == n) ans++;

这种写法虽然代码更长，但逻辑更清晰，也更容易排查错误。

6.3 交换循环顺序（当 m 较大时）

当 m 的值较大时，可以考虑交换 i 和 j 的循环顺序，把范围更小的变量作为外层循环，减少循环嵌套的层数：

cpp

运行

for(int j=0;j<=m;j++){
    for(int i=0;i<=m-j;i++){
        // 判断条件
    }
}

这种优化在理论上可以提高缓存利用率，从而提升程序性能。

七、拓展练习：巩固枚举法应用

7.1 经典百鸡问题

尝试解决最原始的百鸡问题：
"公鸡 5 文钱 1 只，母鸡 3 文钱 1 只，小鸡 3 只 1 文钱。用 100 文钱买 100 只鸡，问公鸡、母鸡、小鸡各买多少只？"

提示：设公鸡、母鸡、小鸡数量分别为 x、y、z，则：

• x + y + z = 100
• 5x + 3y + z/3 = 100
• z 必须是 3 的倍数

7.2 扩展百鸡问题

现有三种物品，单价分别为 a、b、c，要用 n 元钱买 m 个物品，问有多少种购买方案？

这是更通用的问题形式，可以尝试编写一个程序解决这类问题的通用情况。

7.3 换硬币问题

有 1 角、5 角、1 元、5 元、10 元的硬币，要凑出 n 元钱，有多少种不同的凑法？

这也是枚举法的典型应用，可以练习多重循环的使用。

八、知识点总结：从百鸡问题学到的编程思想

8.1 枚举法的应用场景

枚举法是编程中常用的解题方法，特别适合：

• 解的数量有限且可枚举
• 无法找到更高效的数学公式
• 问题规模较小的情况

百鸡问题就是典型的适合用枚举法解决的问题，因为变量的取值范围有限，且没有更简单的公式可以直接计算出结果。

8.2 循环嵌套的逻辑

嵌套循环是处理多变量问题的重要手段：

• 外层循环控制第一个变量
• 内层循环控制第二个变量
• 可以根据外层变量的值动态调整内层循环的范围

在百鸡问题中，我们通过两层嵌套循环分别控制 i 和 j 的取值，实现了对所有可能组合的遍历。

8.3 条件判断的逻辑组合

复杂条件的判断需要使用逻辑运算符组合多个简单条件：

• && 表示 "并且"，只有所有条件都满足时才为真
• || 表示 "或者"，只要有一个条件满足时就为真
• ! 表示 "非"，取反条件的真假

在百鸡问题中，我们使用 && 组合了两个条件，只有当两个条件都满足时，才认为是有效方案。

8.4 问题转化的思维

解决编程问题的关键是将实际问题转化为程序可以处理的形式：

• 识别问题中的变量和常量
• 找出变量之间的数学关系
• 确定解的约束条件
• 设计算法遍历可能的解并验证

百鸡问题的解决过程就是一个典型的问题转化过程：从实际的购买问题，转化为不定方程的求解问题，再转化为枚举验证的算法。

九、PPT 展示建议

如果用这篇内容制作 PPT，可以按照以下结构组织，突出重点，方便讲解：

1. 封面页：

   • 标题：洛谷 B3836 [GESP202303 二级] 百鸡问题
   • 副标题：枚举法求解不定方程
   • 背景图：古代算书或鸡的图片

2. 题目介绍页：

   • 简洁描述题目要求
   • 列出输入输出格式
   • 展示 1-2 个示例（用表格形式展示输入和输出）

3. 数学模型页：

   • 列出问题中的两个方程
   • 用图示展示变量之间的关系
   • 说明解的约束条件（非负整数）

4. 解题思路页：

   • 用流程图展示解题步骤
   • 突出枚举法的核心思想
   • 说明变量范围的确定方法

5. 代码框架页：

   • 展示完整代码
   • 用不同颜色标注关键部分
   • 简要说明代码结构

6. 代码解析页（分 2-3 页）：

   • 逐行解释代码含义
   • 重点讲解循环范围和条件判断
   • 用动画展示变量变化过程

7. 执行过程演示页：

   • 以示例输入为例
   • 分步展示循环执行过程
   • 用表格记录每次判断的结果

8. 易错点分析页：

   • 列出常见错误类型
   • 展示错误代码和正确代码的对比
   • 给出避免错误的建议

9. 优化思路页：

   • 介绍几种优化方法
   • 对比优化前后的代码
   • 分析优化带来的好处

10. 总结与拓展页：

    • 提炼核心知识点
    • 推荐相关练习题目
    • 总结枚举法的应用场景

十、写在最后

百鸡问题虽然是一道简单的入门级编程题，但它蕴含了丰富的编程思想和数学知识。通过解决这道题，我们不仅学会了具体的解题方法，更重要的是掌握了枚举法这一重要的编程工具，理解了如何将实际问题转化为程序可以处理的形式。

在编程学习的初期，这类经典问题是很好的练习材料。它们不仅能帮助我们熟悉语法结构，更能培养我们的逻辑思维能力和问题转化能力。

记住，编程的核心不是记住代码，而是理解问题、分析问题、解决问题的思维过程。当你真正掌握了这些思维方法，就能举一反三，解决更多更复杂的问题。

希望这篇博客能帮助你更好地理解百鸡问题和枚举法的应用。如果有任何疑问或建议，欢迎在评论区留言讨论！