POJ-2142[The Balance]拡張ユークリッド

标题:Ax+By=C;一組の解xを求めて、yはabs(x)+abs(y)を最小にして、abs(x)+abs(y)が等しいならば、(A*abs(x)+B*abs(y))を最小にします
 
解法:解がある場合、まずxを最小正数にする解のセットを得て、それからx、y異号が停止するまで、それぞれ上と下に列挙して、その間に答えを更新し続けます.x-dx毎にy+dy
 
CODE:

/*      */
/*AC  ：0ms*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <memory.h>
#include <cmath>
using namespace std;
int A,B,C;
int ans_x,ans_y,Min;
int extgcd(int a,int b,int &x,int &y)
{
	if(b==0) {x=1;y=0;return a;}
	int d=extgcd(b,a%b,x,y);
	int t=x;x=y;y=t-a/b*y;
	return d;
}
int main()
{
	int w,dx,dy,X,Y,x,y,temp;
	while(scanf("%d%d%d",&A,&B,&C)!=EOF)
	{
		if(A==0&&B==0&&C==0) break;
		w=extgcd(A,B,X,Y);
		if(C%w) printf("no solution
");
		else
		{
			X*=C/w;
			dx=B/w;
			dy=A/w;
			X=(X%dx+dx)%dx;
			Y=(C-A*X)/B;
			ans_x=abs(X);ans_y=abs(Y);
			Min=abs(X)+abs(Y);
			//printf("@%d %d %d %d
",X,Y,dx,dy);
			// X,Y      ,  x,y  
			x=X;y=Y;
			while(true)//    
			{
				if(x>0&&y<0) break;
				x+=dx;y-=dy;
				temp=abs(x)+abs(y);
				if(temp<Min)//    
				{
					ans_x=abs(x);
					ans_y=abs(y);
					Min=temp;
				}
				else if(temp==Min)
				{
					if((A*abs(x)+B*abs(y))<(A*ans_x+B*ans_y))
					{
						ans_x=abs(x);
						ans_y=abs(y);
					}
				}
			}

			x=X;y=Y;
			while(true)//     
			{ 
				if(x<0&&y>0) break;
				x-=dx;y+=dy;
				temp=abs(x)+abs(y);
				if(temp<Min)//    
				{
					ans_x=abs(x);
					ans_y=abs(y);
					Min=temp;
				}
				else if(temp==Min)
				{
					if((A*abs(x)+B*abs(y))<(A*ans_x+B*ans_y))
					{
						ans_x=abs(x);
						ans_y=abs(y);
					}
				}
			}
			printf("%d %d
",ans_x,ans_y);
		}
	}
return 0;
}