百钱买百鸡(四）

• 题目
• • 链接
  • 限制
  • 输入格式
  • 输出格式
  • 数据范围
• 样例输入
• 样例输出
• 题解
• AC代码

题目

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

链接

T1375 百钱买百鸡(四)

限制

时间：1000ms
内存：131072K

输入格式

输入一个正整数 n

输出格式

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

数据范围

1≤n≤10 ^18

样例输入

100

样例输出

4

题解

n最大可以达10^18，logN级的算法都承受不住，所以肯定存在规律，可以根据该规律去推得答案。
联立：5a + 3b + c/3 = n 和 a + b + c = n；
解得 7a + 4b = 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 
using namespace std;
#define ll long long
int main(void)
{ll n, now, a, b, times, tmp, ii;int flag;while(scanf("%lld", &n) != EOF){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 <= 6; ++j){tmp = i*7 + j*4;if(tmp > n){break;}else if(tmp == n){flag = 1;break;}}if(flag){ii = i;break; }}}cout << (ii/4)+1 << endl; }return 0;
} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！