C/C++经典例题：百钱百鸡

c++程序【百钱买百鸡】的解法

题型介绍：
百鸡问题是一个数学问题，
出自中国古代约5—6世纪成书的《张邱建算经》，
是原书卷下第38题，
也是全书的最后一题，
该问题导致三元不定方程组，
其重要之处在于开创“一问多答”的先例。

问题及解答：
今有鸡翁一，值钱伍；
鸡母一，值钱三；
鸡鶵三，值钱一。
凡百钱买鸡百只，
问鸡翁、母、鶵各几何？
第一种答案：
答曰：鸡翁四，值钱二十；
鸡母十八，值钱五十四；
鸡鶵七十八，值钱二十六。
第二种答案：
又答：鸡翁八，值钱四十；
鸡 母十一，值钱三十三，
鸡鶵八十一，值钱二十七。
第三种答案：
又答：鸡翁十二，值钱六十；
鸡母四、值钱十二；
鸡鶵八十 四，值钱二十八。”
第四种答案（后人补充的）：
又答：鸡翁零，值钱零；
鸡母二十五、值钱七十五；
鸡鶵七十五，值钱二十五。”

现扩展为如果用n元钱买m只鸡，问公鸡 母鸡 小鸡各可买几只？注意：必须把n元钱用完，且每只鸡的个数不得少于0。

聪明的你能通过编写程序解决这个问题吗？

样例输入

100 100

样例输出
0 25 75

4 18 78

8 11 81

12 4 84

分析：直接暴力枚举肯定不行，时间复杂度是n^3，如果用二重循环，很多情况下还是会时间超限，我们可以发现，小鸡的数量肯定是3的倍数，因此只要用一个数组储存0~m里三的倍数就行了，然后求出母鸡和公鸡的只数就行了（虽然本质上来说和二重循环没有区别）

程序如下(2022/6/22 15:41修改)

#include<bits/stdc++.h>
using namespace std;
int a[1005];
int main()
{
  int n,m,q=0;
  cin>>n>>m;
  for(int i=0;i<=m;i+=3){
  	a[++q]=i;
  }
  for(int i=1;i<=q;i++){
  	int t=m-a[i],p=n-(a[i]/3);
  	for(int j=0;j<=t;j++){
  		int k=t-j;
        if(j*5+k*3+a[i]==n&&a[i]+j+k==m) cout<<j<<' '<<k<<' '<<a[i]<<"\n";
	  }
  }
}