Uva 10104 Euclid Problem |x|+|y|最小解 擴展歐幾裡得

[cpp] 
/*
*   url: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1045
*   stratege: 求ax+by=gcd(a,b), |x|+|y|的和的x,y,的解, 擴展歐幾裡得，分四種情況考慮
*   status：10541367 10104   Euclid Problem  Accepted    C++ 0.176   2012-08-30 05:31:09
*   Author: johnsondu  www.2cto.com
*/ 
 
#include <iostream> 
#include <cstdio> 
#include <cmath> 
#include <algorithm> 
#include <cstring> 
using namespace std ; 
 
#define LL long long  
 
void Euclid (LL a, LL b, LL &d, LL &x, LL &y) 
{ 
    if (b == 0) 
    { 
        d = a ; 
        x = 1 ; 
        y = 0 ; 
        return ; 
    } 
    Euclid (b, a%b, d, x, y) ; 
    LL tmp = x ; 
    x = y ; 
    y = tmp - a/b*y ; 
} 
 
LL gcd (LL a, LL b) 
{ 
    return b ? gcd (b, a%b) : a ; 
} 
 
int main () 
{ 
    #if 0 
    freopen ("date.txt", "r", stdin) ; 
    #endif  
    LL a, b, d, x, y, i, c ; 
    LL x0, y0 ; 
    LL ax, ay ; 
    LL tx, ty, mins ; 
    while (scanf ("%lld%lld", &a, &b) != EOF)  // 擴展歐幾裡得,求ax+by = Gcd (a,b)的最小正整數解 
    {                                           //分為4種情況.x的最小正整數,y的最小正整數,x-周期,y-周期 
        Euclid (a, b, d, x, y) ;               //x,y 為 特解, d為a,b 的最大公約數 
        x0 = (x%b + b) % b ;           //x的最小正整數解 （1） 
        y0 = (d-a*x0)/b ;              //相應的y值 
        mins = abs (x0) + abs(y0) ;  
        tx = x0, ty = y0 ; 
         
        x0-=b ;                        //x的最小正整數解-x的周期  (2) 
        y0 = (d-a*x0)/b ;              //此時相應的y 
        if (abs(x0) + abs(y0) < mins) 
        { 
            mins = abs(x0) + abs(y0) ; 
            tx = x0 ; 
            ty = y0 ; 
        } 
         
        y0 = (y%a + a) % a ;           //y的最小正整數解 （3） 
        x0 = (d-b*y0)/a ;              //此時對應的x 
         
        if (abs(x0) + abs(y0) < mins) 
        { 
            mins = abs(x0) + abs(y0) ; 
            tx = x0 ; 
            ty = y0 ; 
        } 
         
        y0 -= a ;                      //y的最小正整數解-y的周期 
        x0 = (d-b*y0)/a ;              //此時對應的x 
        if (abs(x0) + abs(y0) < mins) 
        { 
            mins = abs(x0) + abs(y0) ; 
            tx = x0 ; 
            ty = y0 ; 
        } 
                 
        printf ("%lld %lld %lld\n", tx, ty, d) ;       
    } 
    return 0 ; 
}