题解：百钱买百鸡(四)

计蒜客 T1375

题意：
百钱买百鸡问题：公鸡五文钱一只，母鸡三文钱一只，小鸡三只一文钱，用 100文钱买 100 只鸡，公鸡、母鸡、小鸡各买多少只？
本程序要求解的问题是：给定一个正整数 n，用 n 文钱买 n 只鸡，问公鸡、母鸡、小鸡各买多少只？

输入格式

输入一个正整数 n。

输出格式

如果有解，输出有多少种解（可以用正整数表示的解）。

如果无解，输出"No Answer."。

数据范围

1≤n≤10^18。

样例输入

100

样例输出

4

题解

看这10的18次方，显然，用2层循环是不可能的。连logN级别的解法都难顶。int才21亿啊，才9个零，这直接18个零上来...显然，这是有公式的。

这显然是一个5a+3b+c/3 =n 问有多少解的问题。

题目明显给了提示，n元n鸡，故a+b+c=n；

联立上面两个方程，可以得到一个2元一次方程，即7a+4b=n；

问题转化为以上方程有多少个解。

以样例100为例，从a=100/7=14开始，a逐渐减小，当a==12时，b=4有一个解。

又因为，4和7最小公倍数为28，所以a每减小4，就应有一解，若没有，则此方程组无解。

当然，当n大于4*7-4-7（即17）时，必有解，这是公式。

17特别小，用枚举的方式将前17种可能列举出来就好了。

以下是ac代码：

#include
#include
#include
using namespace std;
#define pb push_back
#define mp make_pair
#define LL long long
#define LD long double
#define fi first
#define se second
#define mem(a,b) memset(a,b,sizeof a)
#define INF 0x7f7f7f7f
#define inf 0x3f3f3f3f
#define sc scanf
#define pf printf
int main(){
    LL n,now,a,b,times,tmp,ii;
    int flag;
        while(~sc("%lld",&n)){
            if(n==1||n==2||n==3||n==5||n==6||n==9||n==10||n==13||n==17){
                puts("No Answer.");
                continue;
            }
            ii=0;
            flag=0;
            now=n/7;
            times=now-5;
            if(now*7==n){
                ii=now;
            }
            else{
                for(LL i=now;i>=times;--i){
                    for(LL j=1;j<=40;++j){
                        tmp=i*7+j*4;
                        if(tmp>n){
                            break;
                        }
                        else if(tmp==n){
                            flag=1;
                            break;
                        }    
                    }
                    if(flag){
                        ii=i;
                        break;
                    }
                }
            if(!flag){
                    puts("No Answer.");
                    continue;
            }
        }
        cout<<(ii/4)+1<<endl;
    }    
    return 0;
}