为防止广告,目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册(新用户需要等待1个小时才能正常使用该功能)。

Sgu/141

来自NOCOW
< Sgu
跳转到: 导航, 搜索
//by mx
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define ABS(x) ((x)>0?(x):(-(x)))
#define SWAP(x,y) {if (x!=y) {x^=y;y^=x;x^=y;}}
#define MAX(x,y) ((x)>(y)?(x):(y))
#define MIN(x,y) ((x)<(y)?(x):(y))
#define R return
long long a,b,p,k,tx,ty,ans,x,y,l,find=0,p1,n1,p2,n2;
long long extended_gcd(long long a,long long b,long long *x,long long *y)
{
	long long d,t;
	if (!b)
	{
		*x=1;
		*y=0;
		R a;
	}
	else
	{
		d=extended_gcd(b,a%b,x,y);
		t=*x;
		*x=*y;
		*y=t-(a/b)*(*y);
		R d;
	}
	R 0;
}
void init()
{
	scanf("%I64d%I64d%I64d%I64d",&a,&b,&p,&k);
	R;
}
void solve()
{
	long long x,y,d,t,tmp,l,X,Y;
	find=0;
	d=extended_gcd(a,b,&x,&y);
	if (p%d)
	{
		printf("NO\n");
		R;
	}
	a/=d;
	b/=d;
	t=p/d;
	p/=d;
	x*=t;
	y*=t;
	if (a<b)
	{
		if (x<0) t=x/b;
		else t=x/b-1;
		x-=t*b;
		y+=t*a;
	}
	else
	{
		if (y<0) t=y/a;
		else t=y/a-1;
		x+=t*b;
		y-=t*a;
	}
	X=x;
	Y=y;
	for (l=-10;l<=10;l++)
	{
		x=X-l*b;
		y=Y+l*a;
		t=ABS(x)+ABS(y);
		if (!((t-k)&1)&&(!find||t<ans))
		{
			ans=t;
			tx=x;
			ty=y;
			find=1;
		}
	}
	if (!find||k<ans)
	{
		printf("NO\n");
		R;
	}
	if (tx<0) n1=-tx;
	else p1=tx;
	if (ty<0) n2=-ty;
	else p2=ty;
	long long i;
	k-=ans;
	k/=2;
	p2+=k,n2+=k;
	printf("YES\n%I64d %I64d %I64d %I64d\n",p1,n1,p2,n2);
	R;
}
int main()
{
	init();
	solve();
	R 0;
}
个人工具