百鸡问题 题解

题目分析

经典的“百鸡问题”是求解一个三元一次不定方程组：

[
\begin{cases}
\text{公鸡数} + \text{母鸡数} + \text{小鸡数} = m \
x \cdot \text{公鸡数} + y \cdot \text{母鸡数} + \dfrac{\text{小鸡数}}{z} = n
\end{cases}
]

其中公鸡、母鸡、小鸡的数量都是非负整数。题目将经典的参数一般化：公鸡 (x) 元一只，母鸡 (y) 元一只，小鸡 (z) 只一元。给定总钱数 (n) 和总鸡数 (m)，需要求出所有满足条件的购买方案数。

数据范围很小（(x,y,z \le 10)，(n,m \le 1000)），我们可以直接使用暴力枚举所有可能的公鸡和母鸡数量，然后计算出小鸡的数量，并验证是否满足条件。

解题思路

设公鸡数量为 (a)，母鸡数量为 (b)，小鸡数量为 (c)。由总数量条件可得：
[
c = m - a - b
]
由总金额条件可得：
[
x \cdot a + y \cdot b + \frac{c}{z} = n
]
因为钱数必须是整数，小鸡的数量 (c) 必须是 (z) 的倍数。

因此，一个三元组 ((a,b,c)) 合法的条件是：

1. (a, b, c \ge 0) 且为整数；
2. (a + b + c = m)；
3. (x \cdot a + y \cdot b + c / z = n)，且 (c) 能被 (z) 整除。

由于 (n) 和 (m) 只有 (1000)，可以枚举公鸡数量 (a)（从 (0) 到 (\min(n/x, m))），再枚举母鸡数量 (b)（从 (0) 到 (\min((n - x \cdot a)/y, m - a))），然后计算出小鸡数量 (c = m - a - b)，最后检查金额等式是否成立且 (c) 能否被 (z) 整除即可。如果满足，方案数加一。

另一种等价的做法（参考代码中使用的方法）是：由金额等式计算出小鸡数量 (c = (n - x \cdot a - y \cdot b) \times z)，再检查总数等式 (a + b + c = m)。这两种方法的本质相同，本文采用第一种更直观的检查方式。

算法说明

1. 读入 (x, y, z, n, m)。
2. 初始化答案计数器 ans = 0。
3. 外层循环枚举公鸡数 gj：gj 从 0 到 min(n/x, m)。
   • 内层循环枚举母鸡数 mj：mj 从 0 到 min((n - gj*x)/y, m - gj)。
     • 计算小鸡数 xj = m - gj - mj。
     • 检查是否满足：
       • xj >= 0
       • xj % z == 0
       • gj * x + mj * y + xj / z == n
     • 如果全部满足，ans 增加 1。
4. 输出 ans。

时间复杂度分析

公鸡数量最多为 (\min(n/x, m) \le 1000)，母鸡数量同样最多为 (1000)，因此循环次数上限约为 (10^6) 级别。内层检查是 (O(1)) 的，因此总时间复杂度为 (O((n/x) \times (n/y)))，在本题数据范围内（(n\le 1000)）完全可以接受，远未达到时间限制。

代码实现

以下给出 C++ 完整代码，并附有详细注释。

cpp
复制
1#include <iostream>
2using namespace std;
3
4int main() {
5    int x, y, z, n, m;
6    cin >> x >> y >> z >> n >> m;
7
8    int ans = 0; // 方案数
9
10    // 枚举公鸡数量
11    for (int gj = 0; gj * x <= n && gj <= m; ++gj) {
12        // 枚举母鸡数量
13        for (int mj = 0; mj * y + gj * x <= n && mj + gj <= m; ++mj) {
14            // 根据总数计算小鸡数量
15            int xj = m - gj - mj;
16            if (xj < 0) continue;               // 小鸡数量非负
17            if (xj % z != 0) continue;          // 小鸡数量必须是z的倍数
18            // 检查金额是否恰好为n
19            if (gj * x + mj * y + xj / z == n) {
20                ++ans;
21            }
22        }
23    }
24
25    cout << ans << endl;
26    return 0;
27}

代码说明

• 变量 gj、mj、xj 分别表示公鸡、母鸡、小鸡的数量。
• 外层循环条件 gj * x <= n && gj <= m 确保公鸡的花费不超过总钱数，且数量不超过总鸡数，进行剪枝，减少无效枚举。
• 内层循环同理，在公鸡数量固定的前提下，限制母鸡的花费和数量。
• 计算小鸡数量 xj = m - gj - mj 来源于总数等式，然后判断是否为非负数、能否被 (z) 整除，以及金额等式是否成立。
• 每找到一种合法方案，计数器 ans 自增。
• 最后输出 ans。

样例验证

样例输入：

5 3 3 100 100

程序运行过程会找到 4 种方案（正如提示所示），输出 4。

总结

本题是经典百鸡问题的参数化扩展，数据范围极小，直接枚举所有可能的公鸡和母鸡数量，并利用总鸡数和总钱数等式验证即可。通过合理的循环边界剪枝，保证了在给定限制下高效运行。这道题考察了暴力枚举和数学关系验证的基本功，适合初学者练习。