通过两层循环枚举鸡翁和鸡母的数量,根据百鸡计算鸡雏数量,并判断钱数是否等于一百。
OJ: roj
题目 ID: 5030
难度:入门
标签:暴力枚举
创建: 2026-10-08 19:48
更新: 2026-10-08 19:48
形式化题目
已知鸡翁每只
即求满足以下条件的所有非负整数解
输出格式:每行输出一组解的
正解
思路
这是一道经典的枚举题目。
朴素的做法是写三重循环,分别枚举
优化思路:
- 由于总数为
,只要确定了 和 , 的值就固定为 。这样可以省去 的枚举,将复杂度降为两重循环。 - 进一步缩小枚举范围:
- 鸡翁
钱一只,最多买 只,因此循环条件为 。 - 鸡母
钱一只,最多买 只,因此循环条件为 。
- 鸡翁
- 对每个确定的
和 ,求出 。判断是否满足: 是 的倍数(因为鸡雏是按 只一组卖的) 如果全满足,则找到了一组解。题目要求按依次由小到大输出,我们的外层循环正是以 从小到大枚举的,所以天然给出了升序输出。
代码
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 19:45
# update_at: 2026-10-08 19:45
TOTAL = 100 # 百钱买百鸡:鸡共 100 只、钱共 100 文
ROOSTER_PRICE = 5 # 鸡翁一只值钱 5
HEN_PRICE = 3 # 鸡母一只值钱 3
CHICK_PER_COIN = 3 # 鸡雏 3 只值钱 1,所以鸡雏数必须是 3 的倍数
def solve() -> None:
"""枚举鸡翁、鸡母并推出鸡雏,校验钱数后按鸡翁升序输出全部解。"""
for rooster in range(TOTAL // ROOSTER_PRICE + 1):
for hen in range(TOTAL // HEN_PRICE + 1):
chick = TOTAL - rooster - hen
if chick < 0 or chick % CHICK_PER_COIN:
continue # 鸡雏按 3 只一组卖,数量不是 3 的倍数时钱数无意义
cost = rooster * ROOSTER_PRICE + hen * HEN_PRICE + chick // CHICK_PER_COIN
if cost == TOTAL:
print(rooster, hen, chick)
if __name__ == "__main__":
solve()cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-08 19:45
* update_at: 2026-10-08 19:45
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll TOTAL = 100; // 百钱买百鸡:鸡共 100 只、钱共 100 文
const ll ROOSTER_PRICE = 5; // 鸡翁一只值钱 5
const ll HEN_PRICE = 3; // 鸡母一只值钱 3
const ll CHICK_PER_COIN = 3; // 鸡雏 3 只值钱 1,所以鸡雏数必须是 3 的倍数
// 枚举鸡翁数、鸡母数,由「百鸡」推出鸡雏数,再校验「百钱」。
// 鸡翁从小到大枚举,输出天然按鸡翁升序,符合题面「依次由小到大」。
void solve() {
for (ll rooster = 0; rooster * ROOSTER_PRICE <= TOTAL; rooster++) {
for (ll hen = 0; hen * HEN_PRICE <= TOTAL; hen++) {
ll chick = TOTAL - rooster - hen;
// 鸡雏按 3 只一组卖,不能整除就没有对应钱数,直接跳过
if (chick < 0 || chick % CHICK_PER_COIN != 0) {
continue;
}
ll cost = rooster * ROOSTER_PRICE + hen * HEN_PRICE + chick / CHICK_PER_COIN;
if (cost == TOTAL) {
cout << rooster << " " << hen << " " << chick << "\n";
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}复杂度
- 时间复杂度:
,其中 。外层循环执行 次,内层循环执行 次,总共约进行 次判断,复杂度为常数级别 ,非常小。 - 空间复杂度:
,只需常数级别的变量用于循环和计算。
总结
经典的一道利用等式约束减少循环层数的枚举题。 关键点及容易踩坑的地方如下:
- 隐藏条件与等价方程:本题等价于解三元一次方程组:
将第一个式子的代入第二个式子,可以消元得到: 由此可得必须是 4 的倍数(因为 和 都是 4 的倍数)。所以解的 只能是 。这也解释了为何最终只有这 4 组解( 已经被排除)。 - 截断除法陷阱:鸡雏的价值是
钱一只,说明鸡雏的数量 必须是 的倍数。必须加上 chick % 3 == 0的判断。如果不用这个判断,而是直接算整数除法chick / 3或向下取整chick // 3,在 C++ 和 Python 中会发生截断,从而把本来不成立的解(花费变少)错误地判定为等于。 - 输出顺序与格式:题目要求依次由小到大输出。通过将
放在外层循环从小到大枚举,输出天然就是按 升序的。另外,每行输出三个数并用空格隔开,末尾单个换行,且不要带有多余空行。