Poj 2142 The Balance(拡張ユークリッドアルゴリズム)

題意:2種類の分銅があり、それぞれの分銅の品質aとbは、現在、品質dと呼ばれるものが要求されており、天秤の両側に分銅を置くことができ、aの数量xとbの数量yが最小であり、x+yの値が最小であることが要求されている.

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;

int a,b,c,x,y;

int exgcd(int a,int b)
{
    int t,d;
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    d=exgcd(b,a%b);
    t=x;
    x=y;
    y=t-(a/b)*y;
    return d;
}

int main()
{
    int sum1,sum2,ans1,ans2;
    int a1,b1,c1;
    while(scanf("%d%d%d",&a,&b,&c),a||b||c)
    {
        int d=exgcd(a,b);
        a1=a/d;
        b1=b/d;
        c1=c/d;
        x=x*c/d;
        y=y*c/d;
        sum1=abs(x)+abs(y);
        sum2=abs(x)*a+abs(y)*b;
        ans1=abs(x);
        ans2=abs(y);
        for(int i=-50000; i<=50000; i++)   // x1=x+b/d*t; y1=y-a/d*t;
        {
            int s1=abs(x+i*b1)+abs(y-i*a1);
            int s2=abs(x+i*b1)*a+abs(y-i*a1)*b;
            if(s1<sum1||s1==sum1&&s2<sum2)
            {
                sum1=s1;
                sum2=s2;
                ans1=abs(x+i*b1);
                ans2=abs(y-i*a1);
            }
        }
        printf("%d %d
",ans1,ans2);
    }
    return 0;
}