Codeforces Round #592 (Div. 2) C (exgcd)

タイトルリンク
C. The Football Season
タイトル:
4つの数字n,p,w,d n,p,w,d,p,w,dが与えられ、x,y x,y x,y x,yが求められ、x+y<=n&&w
考え方:
第2の式の解に対して必然的にg c d(w,d)∣p gcd(w,d)|p gcd(w,d)∣pを満たす必要があり、その後e x g c d exgcdによってx,y x,y x,yの1つの解を求めることができ、その後、モジュールによって1つの変数の最小正解を得ることができ、それによって別の変数を求めることができ、合否を判断すればよい.
コード:

#include 
#define ll long long
using namespace std;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0)
	{
		x=1;y=0;
		return a;
	}
	ll gcd=exgcd(b,a%b,x,y),t=x;
	x=y;y=t-(a/b)*y;
	return gcd;
}
long long n,p,w,d;
ll x,y,z;
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	cin>>n>>p>>w>>d;
	ll t=exgcd((ll)w,(ll)d,x,y);
	if(p%t!=0){
		puts("-1");return 0;
	}
	if(d>=w){///    ，    ll
		x=((p/t)%(d/t)*x%(d/t)+(d/t))%(d/t);
		y=(p-w*x)/d;
		if(x>=0&&y>=0&&x+y<=n){
			printf("%lld %lld %lld
",x,y,n-x-y);
		}else puts("-1");
	}else{
		y=((p/t)%(w/t)*y%(w/t)+(w/t))%(w/t);
		x=(p-d*y)/w;
		if(x>=0&&y>=0&&x+y<=n){
			printf("%lld %lld %lld
",x,y,n-x-y);
		}else puts("-1");
	}
}