[poj] 2142 The Balance

原题

显然ex_gcd板子题

#include<cstdio>
using namespace std;
int a,b,c,gg,p1,q1,p2,q2,x,y;

int ex_gcd(int a,int b,int &x,int &y)
{
    int r;
    if (!b)
    {
	x=1;
	y=0;
	return a;
    }
    r=ex_gcd(b,a%b,y,x);
    y-=a/b*x;
    return r;
}

int main()
{
    while (~scanf("%d%d%d",&a,&b,&c))
    {
	if (!a && !b && !c) break;
	gg=ex_gcd(a,b,x,y);
	a/=gg;
	b/=gg;
	c/=gg;
	p1=(x*c%b+b)%b;
	q1=(c-p1*a)/b;
	if (q1<0) q1=-q1;
	q2=(y*c%a+a)%a;
	p2=(c-q2*b)/a;
	if (p2<0) p2=-p2;
	if (p1+q1>p2+q2 || (p1+q1==p2+q2 && a*p1+b*q1>a*p2+b*q2))
	    p1=p2,q1=q2;
	printf("%d %d
",p1,q1);
    }
    return 0;
}