题意

求解

$$ \left\{ \begin{aligned} & wx+dy=p \\ & x+y \le n \\ & x,y\ge 0 \end{aligned} \right. $$

的一组解$(x,y)$

数据范围：$2 \le n \le 10^{12},1 \le p \le 10^{17},1 \le d < w \le 10^5$

题解

因为$d<w$，显然在满足第一个式子的时候$x$越大（$y$越小）更能使第二个式子得到满足
证明：第一个式子可用扩展欧几里得算法求得特解$(x_0,y_0)$；而调整解的时候，$x_0$增加$\frac{d}{gcd(w,d)}$，$y_0$对应减少$\frac{w}{gcd(w,d)}$，因为$d<w$，所以$x_0+y_0$减少$\frac{w}{gcd(w,d)}-\frac{d}{gcd(w,d)}>0$，和变小，更优
不必使用扩展欧几里得算法求得特解，此时求得满足条件的最小$y$即可
将一式左右两边都除以$gcd(w,d)$，再考虑一式在模$w$意义下的情况$$dy \equiv p \ (\bmod w)$$
所以$$y \equiv \frac{p}{d} \ (\bmod w)$$
即为最小的满足条件的$y$（此处使用扩展欧几里得算法求$d$关于$w$的逆元）
而此时$$x=\frac{p-dy}{w}$$
再验证满足答案即可

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
#define int long long
int n,p,w,d,x,y,g;
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    int gcd=exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return gcd;
}
inline int inv(int x,int p){
    int x0,y0;
    exgcd(x,p,x0,y0);
    return (x0%p+p)%p;
}
signed main(){
    scanf("%lld%lld%lld%lld",&n,&p,&w,&d);
    g=gcd(w,d);
    if(p%g!=0){
        puts("-1");
        return 0;
    }
    p/=g,w/=g,d/=g;
    y=p%w*inv(d,w)%w,x=(p-y*d)/w;
    if(x<0 || x+y>n){
        puts("-1");
        return 0;
    }
    printf("%lld %lld %lld",x,y,n-x-y);
    return 0;
}