G2001 [GESP202303 二级] 百鸡问题 题解

知识点：枚举、方程、计数。

解题思路

枚举公鸡数a和母鸡数b，小鸡数唯一为m-a-b。只有小鸡数能被z整除，且ax+by+(m-a-b)/z等于预算n时计数。

为什么正确

每种分配唯一对应一对(a,b)，枚举不会遗漏；数量和费用两个条件共同保证合法。

易错点

小鸡价格按z只一元计算，必须先判断整除；允许某一类数量为0。

复杂度

时间O(m²)，空间O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int x,y,z,n,m,ans=0;
    cin>>x>>y>>z>>n>>m;
    for(int a=0;a<=m;a++)for(int b=0;b+a<=m;b++) {
        int c=m-a-b;
        if(c%z==0&&a*x+b*y+c/z==n)ans++;
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用10个自行生成的测试点。