題目鏈接
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.uj5u.com/houduan/96302.html
標籤：C++
上一篇：BF演算法（蠻力匹配）
下一篇：CF1244F Chips