蓝桥杯1427: -买不到的数目（百钱百鸡问题变体）

百钱白鸡问题：

公鸡5钱一只，母鸡3钱一只，小鸡1钱3只。100钱买100只鸡，问公鸡，母鸡，小鸡各几只？

问题实质是求不定方程的整数解（数论）：

a+b+c=100①

5a+3b+c/3=100②

思路：穷举法（暴力搜索）

方程②可变形为15a+9b+c=300,这样做可以防止出现整数除问题]

a的可能取值范围是[0,20],b的可能取值范围是[0,33],c的可能取值范围是[0,100]

可以用三个for循环遍历abc判断①②是否都成立

优化：

当a,b确定时，c=100-a-b，c也确定了，所以可以把三重循环降为两重循环

进一步优化：

①②消元，可以消掉c，得到7a+4b = 100③

a的取值为[0,14],b=(100-7a)/4

在循环a时，判断b是否为整数,和a+b+c是否为100   即可

代码：

for (int i = 1; i <= 14; ++i) {
		if ((100 - 7 * i) % 4 == 0) {
			int y = (100 - 7 * i) / 4;
			int z = 100 - i - y;
			if (i + y + z == 100) {
			cout< 
 
 
 
 猜想：结果在max(m,n)和m*n之间
 
am+bn=i   ,  max(m,n)<=i<=m*n
 
遍历a，判断b是否为整数即可
 
#include
#include
using namespace std;
int main()
{
	int maxa=0;
	int m,n;
	cin>>m;
	cin>>n;
	int begin=max(m,n);
	int end=m*n;
	int time=end/m; 
	for(int i=begin;i<=end;i++)
	{
		//判断i是否能由m，n构成
		bool flag=false;
		 for(int j=0;j<=time;j++)
		 {
		 	if(i-j*m<0)
		 	break;
		 	if((i-j*m)%n==0)
		 	{
		 		//i能构成
				 flag=true;
				 break; 
			 }
		  }
		  if(flag==false)
		  {
		  	maxa=max(maxa,i);
		   } 
	}
	cout<