poj - 2142 - The Balance

題意:x個のaミリグラムの分銅とy個のbミリグラムの分銅でちょうど質量dミリグラムのアスピリンと呼ばれ、x+yを最小にするxとyを求める.
タイトルリンク:http://poj.org/problem?id=2142
——>>いい問題ですね.ユークリッド拡張アルゴリズムはax+by=gcd(a,b)しか求められないからである.そこで、まずa,bの最大公約数gcd_を求めるab、ax+by=dについて、a,b,dをgcd_で除算するabは、次いで、(a/gcd_ab)x+(b/gcd_ab)y=1の最小整数解を求めることができ、その後、求められたこれらの解のセットにd/gcd_を乗算するabはx 0,y 0を得て、ax+by=dの1組の解で、数論の知識からax+by=dのすべての解を得ます:x=x 0-bt,y=y 0+at(tはパラメータです)、それでは|x|+|y|を最小にして、x=0に1組の解を求めて、更にy=0に1組の解を求めて、2組は比較的に小さい者を取るのが良いです.

#include <cstdio>

using namespace std;

typedef long long LL;

LL gcd(LL a, LL b)
{
    return b == 0 ? a : gcd(b, a%b);
}
void Euler_extends(LL a, LL b, LL& x, LL& y)
{
    if(!b)
    {
        x = 1;
        y = 0;
    }
    else
    {
        Euler_extends(b, a%b, y, x);        //        ，    ，  ！
        y -= a / b * x;
    }
}
int main()
{
    LL a, b, d, x, y;
    while(~scanf("%I64d%I64d%I64d", &a, &b, &d))
    {
        if(!a && !b && !d) return 0;
        LL gcd_ab = gcd(a, b);
        a /= gcd_ab;
        b /= gcd_ab;
        d /= gcd_ab;
        Euler_extends(a, b, x, y);
        LL y1 = (y * d % a + a) % a;
        LL x1 = (d - b * y1) / a;
        if(x1 < 0) x1 = -x1;
        LL x2 = (x * d % b + b) % b;
        LL y2 = (d - a * x2) / b;
        if(y2 < 0) y2 = -y2;
        if(x1+y1 < x2+y2) printf("%I64d %I64d
", x1, y1);
        else printf("%I64d %I64d
", x2, y2);
    }
    return 0;
}