CF1244C The Football Season
2019-10-16 07:51:22来源:博客园 阅读 ()
CF1244C The Football Season
题目链接
problem
给定\(n,p,w,d\),求解任意一对\((x,y)\)满足\[xw+yd=p\\ x + y \le n\]
\(1\le n\le 10^{12},0\le p\le 10^{17},1\le d<w \le 10^5\)
solution
注意到\(n,p\)非常大,\(w,d\)比较小。而且\(w>d\)。所以我们就想让\(y\)尽量小。
实际上如果最终有解,那在\(y\le w\)中肯定有解。
证明如下:
如果有\(y'=aw+k(a\ge 1,0\le k < w)\)使得\(xw+y'd=p\)。即\(xw+(aw+k)d=xw+awd+kd=(x+ad)w+kd=p\)。
发现\(xw+(aw+k)d\)的系数和为\(x+aw+k\)。\((x+ad)w+kd\)的系数和为\(x+ad+k\)。又因为\(w>d\)。所以后者的系数和要小。所以\(d\)的系数一定小于等于\(w\)
然后在区间\([0,w]\)中枚举\(y\)。计算\(x\)即可。
code
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
#include<map>
#include<string>
using namespace std;
typedef long long ll;
ll read() {
ll x = 0,f = 1; char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0',c = getchar();}
return x * f;
}
int main() {
ll n = read(),p = read(),w = read(),d = read();
for(ll y = 0;y <= w;++y) {
if((p - y * d) % w) continue;
ll x = (p - y * d) / w;
if(x >= 0 && x + y <= n) {
printf("%I64d %I64d %I64d\n",x,y,n - x - y);
return 0;
}
}
puts("-1");
return 0;
}
原文链接:https://www.cnblogs.com/wxyww/p/CF1244C.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:BF算法(蛮力匹配)
下一篇:CF1244F Chips
- SGU 132 Another Chocolate Maniac 2020-03-06
- 协程的原理(Coroutine Theory) 2020-02-23
- 二叉堆(2)LeftistHeap 2020-02-19
- Boost C++ 库 中文教程(全) 2019-12-19
- Run-Time Check Failure #0 - The value of ESP was not pro 2019-11-11
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash