大家好，这次来讲百钱买百鸡（3），如果错过前两期的的回顾一下百钱买百鸡（2) 和 百钱买百鸡
题目如下
通过上一期的分析，我们知道这次n的范围很大，所以时间复杂度不可能为O（n^3)，而需要是O（n^2）。分析题目，我们发现可以得到两个方程如下：
当公鸡数量=a，母鸡数量=b，小鸡数量=c，价格/鸡的数量=n时，
a+b+c=n，5a+3b+1/3c=n，消去c，得到7a+4b=n，所以不需要知道小鸡有几只，直接算母鸡与公鸡数量即可
所以，我们将原代码
for(int x=0;x5;x++){for(int i=0;i3;i++){int j=n-x-i;if(j%3==0){if(5*x+3*i+j/3==n){cout" "" "endl;c=1;}}}}
修改为
for(int x=0;x5 && j==0;x++) // 遍历公鸡的数量{for(int i=0;i3;i++) // 遍历母鸡的数量{if(7*x+4*i==n) //当以上方程（7a+4b=n）成立时{xx=x; //记录此时公鸡数量ii=i; //记录此时母鸡数量c=1; //不会出现无解情况j=1; //停止循环}}}
有不定方程7a+4b=n时，只要找到a，b的一组解a=x,b=y，即可获得a，b通解为
a=x±4k，b=y±7k
而我们此时的a，b都是从小到大便利的，所以我们就可以通过while循环来计算有几组解，得到代码如下
while(true){if(xx0 || ii0) //循环停止条件（当公鸡或母鸡中一值小于0，不可能发生）{break; //停止循环}xx+=4; //代入通解ii-=7; //代入通解l++; //解法增加}
通过如上代码，可以获得一共有多少组解，于是最后，我们只需输出即可
if(c==0){cout"No Answer.";}else{cout}
最终，我们获得完整代码
using namespace std;int main(){int n,c=0,xx=0,ii=0,l=0,j=0;cin>>n;for(int x=0;x5 && j==0;x++) // 遍历公鸡的数量{for(int i=0;i3;i++) // 遍历母鸡的数量{if(7*x+4*i==n) //当以上方程（7a+4b=n）成立时{xx=x; //记录此时公鸡数量ii=i; //记录此时母鸡数量c=1; //不会出现无解情况j=1; //停止循环}}}while(true){if(xx0 || ii0) //循环停止条件（当公鸡或母鸡中一值小于0，不可能发生）{break; //停止循环}xx+=4; //代入通解ii-=7; //代入通解l++; //解法增加}if(c==0){cout"No Answer.";}else{cout}return 0;}
本题难度大约在csp—j第二题左右的水平，需要一定的数学知识，所以还是有些难度哦，这已经是百钱买百鸡的第三期了，下次就是最后一期，先来看看题目吧
我们可以看到这里的数据范围直接达到了10^18，整整比上次的的时间复杂度高了10^10倍，这次的题目难度瞬间提升，与第二题根本无法相比，那么，这道题应该怎么做呢，还是1周时间，大家想想吧