题解

题目解析

• 输入输出：输入五个整数 $x, y, z, n, m$，分别表示公鸡单价（元）、母鸡单价（元）、小鸡 $z$ 只售价（元）、总预算（元）、需要购买的总鸡数；输出满足条件的购买方案总数 $C$。
• 数据范围：$1 \leq x, y, z \leq 10$，$1 \leq n, m \leq 1000$。数据规模较小，允许使用枚举策略。
• 复杂度要求：时间复杂度 $O\left(\frac{n^2}{x \cdot y}\right)$，最坏情况下约 $10^6$ 次运算，远低于 $1\text{s}$ 限制；空间复杂度 $O(1)$。
• 算法知识点：枚举（暴力求解）、不定方程整数解

思路解析

这是一个典型的不定方程整数解计数问题。设购买公鸡、母鸡、小鸡的数量分别为 $a, b, c$，可列出方程组：

$$\begin{cases} a \cdot x + b \cdot y + \frac{c}{z} = n \\ a + b + c = m \\ a, b, c \geq 0 \text{ 且为整数} \end{cases}$$

直接三重枚举 $a, b, c$ 会达到 $O(m^3)$ 的复杂度，在 $m=1000$ 时不可接受。但注意到 $c$ 可由前两式推导得出，且利用花费作为枚举维度可将范围压缩至 $O(n^2)$：

1. 重新定义枚举变量：设购买公鸡花费 $i$ 元，母鸡花费 $j$ 元，则小鸡花费为 $n - i - j$ 元。

   • 公鸡数量：$a = i / x$
   • 母鸡数量：$b = j / y$
   • 小鸡数量：$c = z \cdot (n - i - j)$（因为每元可买 $z$ 只）

2. 确定枚举边界：

   • $i$ 的范围：$0 \leq i \leq n$，步长为 $x$（确保 $i/x$ 为整数，避免无效状态）
   • $j$ 的范围：$0 \leq j \leq n - i$，步长为 $y$（剩余钱必须非负）

3. 验证可行性：计算总鸡数 $cnt = \frac{i}{x} + \frac{j}{y} + z \cdot (n - i - j)$，若 $cnt = m$ 则方案数 $+1$。

完整代码

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

int main() {
    int x, y, z, n, m;
    cin >> x >> y >> z >> n >> m;
    int ans = 0;
    
    // i: 买公鸡花的钱（步长x确保数量为整数）
    for (int i = 0; i <= n; i += x) {
        // j: 买母鸡花的钱，上限为剩余钱n-i（步长y确保数量为整数）
        for (int j = 0; i + j <= n; j += y) {
            int money_chick = n - i - j;          // 买小鸡的钱
            int cnt_chick = z * money_chick;      // 小鸡数量：每元z只
            int total = i / x + j / y + cnt_chick; // 总鸡数
            
            if (total == m) 
                ans++;
        }
    }
    
    cout << ans << endl;
    return 0;
}