The Balance （poj 2142）

  题目大意：

  给你三个自然数a,b,c，让你求一组x,y使得（a*x + b*y == 1）且（|x|+|y|）最小，若（|x|+|y|）相同则使得（a*|x|+b*|y|）最小。

  题解：

    我们可以使用扩欧轻易求出一组（x0,y0）,但怎么才能让（|x|+|y|）最小呢？

   我们设 d = gcd(a,b) ， a > b

   由 x = x0 + t*b/d , y = y0 - t*a/d （t为整数）可以发现y的变化率大于x的变化率，那么我们可以联想到让|y|尽量小。那么这种策略对不对呢？

   我们首先考虑当y>0时的情况，若y减小且|x|减小，明显答案更优，若y减小且|x|增大，由于y变化率较大的缘故答案还是更优。

   同理，y<0时y越大答案越优。

   所以我们只要比较y在正数与负数范围内最接近0的两组解即可。

 参考代码：

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

inline int read() {
    int k = 0 , f = 1 ; char c = getchar() ;
    for( ; !isdigit(c) ; c = getchar())
      if(c == '-') f = -1 ;
    for( ; isdigit(c) ; c = getchar())
      k = k*10 + c-'0' ;
    return k*f ;
}

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

int main() {
    int a, b, c ;
    while(1) {
        a = read(), b = read(), c = read() ;
        if(!a && !b && !c) break ;
        bool ss = 0 ;
        if(a < b) {
            swap(a,b) ; ss = 1 ;
        }
        int x, y, d ;
        d = exgcd(a,b,x,y) ;
        x *= (c/d), y *= (c/d) ;
        a /= d, b /= d ;
        while(y < 0) y += a, x -= b ;
        while(y > 0) y -= a, x += b ;
        int add1 = abs(x)+abs(y), add2 = a*d*abs(x)+b*d*abs(y) ;
        y += a, x -= b ;
        if(abs(x)+abs(y) > add1) y -= a, x += b ;
        else if(abs(x)+abs(y) == add1 && a*d*abs(x)+b*d*abs(y) > add2) y -= a, x += b ;
        x = abs(x), y = abs(y) ;
        if(!ss) printf("%d %d
",x,y) ;
        else printf("%d %d
",y,x) ;
    }
    return 0 ;
}