SDUST 软件工程2016-作业4-A 百钱买鸡问题

解决百钱买鸡问题原本并不困难，关键的是这道题对其进行了升级，测试数据太大，传统的解法，像三重循环,二重循环都会导致超时。

这道题正确的解法应该是结合数学方程进行化简，将其转化为1层循环：

x+y+z=n

ax+by+c/d*z=m

由上述两个方程联立可用其他量表示出y来。从而只需要枚举x就能解决该题。

在求方程之后注意要化简，只有能整除的时候才进行整除。最后与m比较的时候因为c/d的问题，所以等式两边同时乘以d以消除误差。

最后千万不要加上z%d==0的条件，因为例如当3元买12小鸡的时候，实际情况是最少买四只小鸡是合法情况不会出现小数，但z%12会变成最少买12只小鸡才是合法情况，所以应该去掉这个条件。

 #include <stdio.h>

 int main(){

     char s[];

     long long  a,b, c, d, m, n;

     gets(s);

     int first=;

     int ok;

     int k=;

     while(scanf("%lld,%lld,%lld/%lld,%lld,%lld",&a,&b,&c,&d,&m,&n)!=EOF){

         k++;

         if(first==)first=;else printf("\n");

         ok=;

         for(long long  i=;i<=m/a;i++){

             long long    j;

             if((m*d-c*n-(a*d-c)*i)%(b*d-c)==)

             j=(m*d-c*n-(a*d-c)*i)/(b*d-c);

             if(j<)continue;

             long long  z=n-i-j;

             if((z*c+i*a*d+j*b*d)==m*d&&z>=){

                 if(!ok)printf("COCKS,HENS,CHICKS\n");

                 ok=;

                 printf("%lld,%lld,%lld\n",i,j,z);

             }

         }

         if(!ok)printf("Cannot buy!\n");

     }

     return ;

 }

SDUST 软件工程2016-作业4-A 百钱买鸡问题的相关教程结束。