题目链接
problem
给定(n,p,w,d),求解任意一对((x,y))满足[xw+yd=p\ x + y le n]
(1le nle 10^{12},0le ple 10^{17},1le d<w le 10^5)
solution
注意到(n,p)非常大,(w,d)比较小。而且(w>d)。所以我们就想让(y)尽量小。
实际上如果最终有解,那在(yle w)中肯定有解。
证明如下:
如果有(y'=aw+k(age 1,0le 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 %i64dn",x,y,n - x - y); return 0; } } puts("-1"); return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/601389.html