CF1244C The Football Season
程序员文章站
2022-05-04 12:22:08
"题目链接" 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 dd$。所以我们就想让$y$尽量小。 实际上如果最终有解,那在$y\le w$中 ......
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; }
上一篇: 原生JS+CSS实现日期插件
下一篇: 回文数字的验证
推荐阅读
-
CF1244C The Football Season
-
Third season nineteenth episode,Ross and Rachel are going to move on?
-
Second season eighth episode,Ross made a list about Rachel,compared to Julie??!!
-
【CodeForces1019E】Raining season(边分治+斜率优化)
-
Codeforces Round #246 (Div. 2) ?B. Football Kit_html/css_WEB-ITnose
-
CF1244C The Football Season
-
Third season nineteenth episode,Ross and Rachel are going to move on?
-
Second season eighth episode,Ross made a list about Rachel,compared to Julie??!!