CF1244C: The Football Season

CF1244C：The Football Season

题意描述：

• 给定(n,p,w,d)，求(x*w+y*d==p)
• 且((x+y)<=n)
• 数据范围：
  • ((1leq nleq10^{12},0leq pleq10^{17},1leq dleq wleq10^5))

思路：

• 求解目标: (x*w+y*d=p)

• 考虑存在一组解

  • [left{ egin{array} =x_0 \y_0=k*w+v(0<v<w)\ end{array} ight. ]

• 则有

  • (x_0*w+y_0*d=p)
  • (x_0*w+(k*w+v)*d=p)
  • (x_0*w+k*d*w+v*d=p)
  • ((x_0+k*d)*w+v*d=p)

• 所以存在一组解

  • [left{ egin{array} =x=x_0+k*d \y=v\ end{array} ight. ]

• 并且由于(w>d)

  • (x+y=x_o+k*d+v<x_0+k*w+v)

• 前者比后者更可能成为答案

• 即(x+y)更有可能小于等于(n)

• 所以直接枚举所有的(v)就好，又因为((0<v<w))，所以最多枚举(1e5)次

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, p, w, d;
int main()
{
    cin >> n >> p >> w >> d;
    for(ll y = 0, x; y < w; y++){
        if((p-d*y)%w==0) x = (p-d*y)/w;
        if(x >= 0 && x + y <= n){
            cout << x << " " << y << " " << n-x-y << endl;
            return 0;
        }
    }
    puts("-1");
    return 0;
}